Ramsey numbers of cycles versus general graphs
Open Access
- 17 February 2023
- journal article
- research article
- Published by Cambridge University Press (CUP) in Forum of Mathematics, Sigma
- Vol. 11, e10
Abstract
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.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- The Ramsey numbers andEuropean Journal of Combinatorics, 2008
- The Cycle-Complete Graph Ramsey NumbersCombinatorics, Probability and Computing, 2005
- The chromatic number of random graphsCombinatorica, 1988
- Generalizations of a Ramsey‐theoretic result of chvátalJournal of Graph Theory, 1983
- Ramsey Numbers Involving Graphs with Long Suspended PathsJournal of the London Mathematical Society, 1981
- The size Ramsey numberPeriodica Mathematica Hungarica, 1978
- Tree‐complete graph ramsey numbersJournal of Graph Theory, 1977
- Ramsey numbers for cycles in graphsJournal of Combinatorial Theory, Series B, 1973
- Generalized Ramsey theory for graphs. III. Small off-diagonal numbersPacific Journal of Mathematics, 1972
- Some remarks on the theory of graphsBulletin of the American Mathematical Society, 1947