### Ramsey numbers of cycles versus general graphs

Combinatorics Seminar

29th November 2022, 11:00 am – 12:00 pm

Fry Building, 2.04

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

## Comments are closed.