| Summary: | 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(Cn, H) = (n−1)(χ(H)−
1) + σ(H), where σ(H) is the minimum possible size of a colour class in a χ(H)-colouring
of H. Allen, Brightwell and Skokan conjectured that the same should be true already when
n ≥ |H|χ(H).
We improve this 40-year-old result of Burr by giving quantitative bounds of the form
n ≥ C|H| log4
χ(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.
|
|---|