An Optimal Bound for Ramsey Goodness of Cycles
Abstract
For graphs F and H, the Ramsey number R(F,H) is the minimum integer N such that every N-vertex graph contains F or its complement contains H. If F is connected and |F|≥σ(H), a construction of Burr gives R(F,H)≥(χ(H)−1)(|F|−1)+σ(H), where σ(H) denotes the minimum order of a color class in a proper χ(H)-coloring of H. Burr proved that this bound is attained for F=Cn when n is sufficiently large. Allen, Brightwell and Skokan conjectured that equality already holds whenever n≥ |H| χ(H), while Haslegrave, Hyde, Kim and Liu subsequently proved it whenever n≥ C|H|log4χ(H). Pokrovskiy and Sudakov conjectured that the optimal linear condition n≥ C|H| suffices; this conjecture was also highlighted by Montgomery in his 2026 ICM survey (see Conjecture 9.2). In this paper, we resolve this conjecture by proving that there is an absolute constant C>0 such that R(Cn,H)=(χ(H)−1)(n−1)+σ(H) for every nonempty graph H and every n≥ C|H|. This gives the first bound linear in |H|, and is best possible up to a constant factor. Our proof builds on the framework of Haslegrave, Hyde, Kim and Liu, and combines some new ideas in expansion and switching cycle lengths.
Related
- Off-diagonal Ramsey numbers for 3-uniform tight hypergraph cycles
- The three-colour bipartite Ramsey number of sufficiently long even cycles
- Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
- The Ramsey threshold for trees versus odd cycles
- Anti-Ramsey Number of Intersecting Odd Cycles
BibTeX
@misc{kuang2026optimal,
title = {{An Optimal Bound for Ramsey Goodness of Cycles}},
author = {Peiru Kuang and Yan Wang},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2607.26956},
eprint = {2607.26956},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.26956},
}
RIS
TY - UNPB
TI - An Optimal Bound for Ramsey Goodness of Cycles
AU - Peiru Kuang
AU - Yan Wang
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2607.26956
UR - https://arxiv.org/abs/2607.26956
AB - For graphs F and H, the Ramsey number R(F,H) is the minimum integer N such that every N-vertex graph contains F or its complement contains H. If F is connected and |F|≥σ(H), a construction of Burr gives R(F,H)≥(χ(H)−1)(|F|−1)+σ(H), where σ(H) denotes the minimum order of a color class in a proper χ(H)-coloring of H. Burr proved that this bound is attained for F=C_n when n is sufficiently large. Allen, Brightwell and Skokan conjectured that equality already holds whenever n≥ |H| χ(H), while Haslegrave, Hyde, Kim and Liu subsequently proved it whenever n≥ C|H|log^4χ(H). Pokrovskiy and Sudakov conjectured that the optimal linear condition n≥ C|H| suffices; this conjecture was also highlighted by Montgomery in his 2026 ICM survey (see Conjecture 9.2). In this paper, we resolve this conjecture by proving that there is an absolute constant C>0 such that R(C_n,H)=(χ(H)−1)(n−1)+σ(H) for every nonempty graph H and every n≥ C|H|. This gives the first bound linear in |H|, and is best possible up to a constant factor. Our proof builds on the framework of Haslegrave, Hyde, Kim and Liu, and combines some new ideas in expansion and switching cycle lengths.
ER -