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⩾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.

Files

Additional details