Ramsey numbers of cycles versus general graphs

Abstract

The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$, provided $n$ is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(\chi (H)-1)+\sigma (H)$, where $\sigma (H)$ is the minimum possible size of a colour class in a $\chi (H)$-colouring of $H$. Allen, Brightwell and Skokan conjectured that the same should be true already when $n\ge |H|\chi (H)$. We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\ge C|H|{\log }^4\chi (H)$, which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number.

20 pages, 3 figures. Final version to appear in Forum of Mathematics, Sigma