The size-Ramsey number of cubic graphs

Abstract

We show that the size-Ramsey number of any cubic graph with $n$ vertices is $O(n^{8/5})$, improving a bound of $n^{5/3+o(1)}$ due to Kohayakawa, Rödl, Schacht, and Szemerédi. The heart of the argument is to show that there is a constant $C$ such that a random graph with $Cn$ vertices where every edge is chosen independently with probability $p\ge C{n}^{-2/5}$ is with high probability Ramsey for any cubic graph with $n$ vertices. This latter result is best possible up to the constant.

15 pages