John Haslegrave

Ramsey numbers of cycles versus general graphs

The Ramsey number R(F,H) is the smallest value of n such that, for every
graph G on n vertices, either G contains a copy of F or its complement
contains a copy of H. In general it is very difficult to get good bounds
on Ramsey numbers, and in particular the best known bounds for the case
when F and H are m-cliques are very far apart.

However, in cases where one of the graphs is sparse, it may be possible to
determine the Ramsey number exactly. Burr and Erdös defined F to be H-good
whenever a specific lower-bound construction for R(F,H) gives the correct
value. Burr proved for any graph H that sufficiently long cycles are
H-good. Allen, Brightwell and Skokan conjectured that it is sufficient for
the cycle to have length at least the product of the order and chromatic
number of H.

Pokrovskiy and Sudakov previously showed that this conjecture is true if
the order of H is sufficiently large in terms of its chromatic number (and
the chromatic number is also sufficiently large). We prove a bound valid
for any graph H, which gives a strengthening of the
Allen-Brightwell-Skokan conjecture for all graphs with chromatic number at
least some constant.

This is joint work with Joseph Hyde (Victoria), Jaehoon Kim (KAIST) and
Hong Liu (IBS).