PC Seminar: Ramsey numbers of cycles versus general graphs

Abstract: 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. However, in cases where one of the graphs is sparse, it may be possible to determine the value 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.

This is a seminar in our seminar series on Probability and Combinatorics (PC).

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