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 C n vertices where every edge is chosen independently with probability p ⩾ 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.