Ramsey numbers of cycles versus general graphs
Forum of Mathematics, Sigma, Tome 11 (2023)
Voir la notice de l'article provenant de la source Cambridge University Press
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\geq \lvert H\rvert \chi (H)$.We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C\lvert H\rvert \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.
@article{10_1017_fms_2023_6,
author = {John Haslegrave and Joseph Hyde and Jaehoon Kim and Hong Liu},
title = {Ramsey numbers of cycles versus general graphs},
journal = {Forum of Mathematics, Sigma},
publisher = {mathdoc},
volume = {11},
year = {2023},
doi = {10.1017/fms.2023.6},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2023.6/}
}
TY - JOUR AU - John Haslegrave AU - Joseph Hyde AU - Jaehoon Kim AU - Hong Liu TI - Ramsey numbers of cycles versus general graphs JO - Forum of Mathematics, Sigma PY - 2023 VL - 11 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.1017/fms.2023.6/ DO - 10.1017/fms.2023.6 LA - en ID - 10_1017_fms_2023_6 ER -
John Haslegrave; Joseph Hyde; Jaehoon Kim; Hong Liu. Ramsey numbers of cycles versus general graphs. Forum of Mathematics, Sigma, Tome 11 (2023). doi: 10.1017/fms.2023.6
Cité par Sources :