For graphs FF and HH, the Ramsey number R(F,H)R(F,H) is the least NN such that every NN-vertex graph contains FF or its complement contains HH. Burr's construction gives R(Cn,H)≥(χ(H)−1)(n−1)+σ(H)R(C_n,H)\ge(\chi(H)-1)(n-1)+\sigma(H), where χ(H)\chi(H) is the chromatic number of HH and σ(H)\sigma(H) is the smallest color class in a χ(H)\chi(H)-coloring of HH; the cycle CnC_n is called HH-good when equality holds. Pokrovskiy and Sudakov conjectured that some absolute constant CC makes CnC_n HH-good for every graph HH with at least one edge and every n≥C∣H∣n\ge C|H|, and Kuang and Wang (2026) proved this, but with an unspecified 'sufficiently large' constant, while star examples force any such constant to be at least 22. The open problem is to determine the optimal constant C∗C^* exactly: currently 2≤C∗2\le C^* and C∗C^* is bounded above only by an ineffective constant, and even for complete bipartite H=Ka,bH=K_{a,b} the best published threshold is n≥2×1049max⁡{b,8}n\ge2\times10^{49}\max\{b,8\}. The focal question is whether C∗=2C^*=2, that is, whether CnC_n is HH-good for every graph HH with at least one edge and every integer n>2∣H∣n>2|H|; whether goodness also holds at the borderline n=2∣H∣n=2|H| decides whether this optimal constant is attained and would in particular settle the Allen–Brightwell–Skokan conjecture for cycles.

Background

For graphs FF and HH, the Ramsey number R(F,H)R(F,H) is the smallest integer NN such that every graph on NN vertices contains FF as a subgraph or its complement contains HH as a subgraph. Exact Ramsey numbers are notoriously hard to determine, and one of the most successful frameworks for exact off-diagonal results (i.e., results where the two graphs differ) is Ramsey goodness, introduced by Burr and Erdős.

Write χ(H)\chi(H) for the chromatic number of HH (the least number of colors needed to color the vertices so that adjacent vertices get different colors), and σ(H)\sigma(H) for the minimum, over all proper χ(H)\chi(H)-colorings of HH, of the size of the smallest color class. Burr observed that when FF is connected and ∣F∣≥σ(H)|F|\ge\sigma(H), the disjoint union of χ(H)−1\chi(H)-1 cliques on ∣F∣−1|F|-1 vertices and one clique on σ(H)−1\sigma(H)-1 vertices contains no copy of FF, while its complement — a complete multipartite graph, i.e., a graph whose vertices split into independent parts with all possible edges between different parts — contains no copy of HH; consequently R(F,H)≥(χ(H)−1)(∣F∣−1)+σ(H)R(F,H)\ge(\chi(H)-1)(|F|-1)+\sigma(H). Following Burr and Erdős, FF is called HH-good when equality holds, meaning this elementary construction already determines the Ramsey number exactly.

Cycles were the classical test case. The Ramsey numbers of two cycles were determined in the 1970s, and Bondy and Erdős proved that the nn-vertex cycle CnC_n is KkK_k-good whenever n≥k2−2n\ge k^2-2; Erdős, Faudree, Rousseau and Schelp conjectured that n≥k≥3n\ge k\ge3 already suffices (apart from the exceptional pair R(C3,K3)R(C_3,K_3)), Nikiforov proved it for n≥4k+2n\ge4k+2, and Keevash, Long and Skokan later showed that for large kk the much weaker condition n≥Clog⁡k/log⁡log⁡kn\ge C\log k/\log\log k suffices, best possible up to the value of the constant CC. For paths versus graphs HH with at least one edge, Pokrovskiy and Sudakov proved that the nn-vertex path PnP_n is HH-good whenever n≥4∣H∣n\ge4|H| — an explicit constant was thus available for paths long before the cycle case.

For cycles versus a graph HH with at least one edge, Burr proved that CnC_n is HH-good for all sufficiently large nn (for each fixed HH), with no effective bound. Allen, Brightwell and Skokan conjectured the explicit threshold n≥χ(H)∣H∣n\ge\chi(H)|H|. Pokrovskiy and Sudakov proved a linear bound n≥1060∣H∣n\ge10^{60}|H| under the additional hypothesis σ(H)≥χ(H)22\sigma(H)\ge\chi(H)^{22}, and conjectured that some absolute constant CC suffices with no hypothesis at all. Haslegrave, Hyde, Kim and Liu came within a logarithmic factor, proving goodness whenever n≥C∣H∣log⁡4χ(H)n\ge C|H|\log^4\chi(H); they also constructed complete multipartite graphs HH for which CnC_n is not HH-good when n=(1−o(1))∣H∣n=(1-o(1))|H|, showing that some linear condition is genuinely necessary, and asked whether the logarithmic factor could be removed. Montgomery's survey for the 2026 International Congress of Mathematicians on expansion methods in graph theory highlighted the Pokrovskiy–Sudakov conjecture as Conjecture 9.2. In July 2026, Kuang and Wang resolved it: there is an absolute constant CC such that R(Cn,H)=(χ(H)−1)(n−1)+σ(H)R(C_n,H)=(\chi(H)-1)(n-1)+\sigma(H) for every graph HH with at least one edge and every n≥C∣H∣n\ge C|H|. Their proof combines a variable-rate form of sublinear expansion (an expansion technique in which the required neighborhood growth of a vertex set depends sublinearly on its size, used to build long paths and cycles of prescribed length) with a 'protected switcher' — an auxiliary structure containing paths of every length in a wide interval, used to adjust a cycle's length to exactly nn.

The resolution, however, says nothing quantitative about the constant. The proof chooses CC 'sufficiently large' and never evaluates it, and even the bipartite case it imports from Pokrovskiy–Sudakov requires n≥2×1049max⁡{b,8}n\ge2\times10^{49}\max\{b,8\} before R(Cn,Ka,b)=n+a−1R(C_n,K_{a,b})=n+a-1 is known. On the other side, goodness can fail for ratios n/∣H∣n/|H| arbitrarily close to 22 from below: take the star H=K1,tH=K_{1,t} (one center vertex joined to tt leaves, so χ(H)=2\chi(H)=2 and σ(H)=1\sigma(H)=1) and n=2t−1n=2t-1; the complete bipartite graph Kt,tK_{t,t} on 2t2t vertices contains no odd cycle, and its complement, two disjoint tt-cliques, has maximum degree t−1t-1 and so contains no K1,tK_{1,t}; hence R(C2t−1,K1,t)≥2t+1>nR(C_{2t-1},K_{1,t})\ge2t+1>n, while (2t−1)/(t+1)→2(2t-1)/(t+1)\to2. Thus any admissible constant is at least 22, and the exact sharp threshold for cycle goodness versus general graphs — the subject of this problem — sits somewhere inside an enormous gap.

Problem Statement

Define

C∗=inf⁡{c≥0: for every graph H with at least one edge and every integer n≥c∣H∣, R(Cn,H)=(χ(H)−1)(n−1)+σ(H)},C^*=\inf\bigl\{c\ge0:\ \text{for every graph }H\text{ with at least one edge and every integer }n\ge c|H|,\ R(C_n,H)=(\chi(H)-1)(n-1)+\sigma(H)\bigr\},

the optimal constant in the linear Ramsey-goodness threshold for cycles versus general graphs. Equivalently, C∗C^* is the supremum of the failure ratios n/∣H∣n/|H| over all pairs (H,n)(H,n) with CnC_n not HH-good; it is an infimum of admissible constants and need not be attained. By the theorem of Kuang and Wang, C∗C^* is finite; by their star example, C∗≥2C^*\ge2. Determine C∗C^* exactly.

Establishing C∗=c0C^*=c_0 amounts to proving that CnC_n is HH-good — i.e., R(Cn,H)=(χ(H)−1)(n−1)+σ(H)R(C_n,H)=(\chi(H)-1)(n-1)+\sigma(H) — for every graph HH with at least one edge and every integer n>c0∣H∣n>c_0|H| for some explicit constant c0c_0, with no hypothesis on χ(H)\chi(H), σ(H)\sigma(H), or the structure of HH; and constructing, for every c<c0c<c_0, a graph HH with at least one edge and an integer n≥c∣H∣n\ge c|H| with CnC_n not HH-good.

The focal case is whether C∗=2C^*=2, that is, whether CnC_n is HH-good for every graph HH with at least one edge and every integer n>2∣H∣n>2|H|; whether goodness also holds at the borderline n=2∣H∣n=2|H| (in contrast to the known failures at n=2∣H∣−3n=2|H|-3) decides whether the infimum is attained, and is part of the determination. If C∗>2C^*>2, the graphs forcing the larger threshold are of independent interest. In either case, the constant must be pinned from both sides.

References

  1. Peiru Kuang, Yan Wang, An Optimal Bound for Ramsey Goodness of Cycles, arXiv:2607.26956 (2026), DOI 10.48550/arxiv.2607.26956, https://arxiv.org/abs/2607.26956
  2. Alexey Pokrovskiy, Benny Sudakov, Ramsey Goodness of Cycles, SIAM Journal on Discrete Mathematics 34 (2020), 1884–1908, DOI 10.1137/18M1199125, arXiv:1807.02313, https://arxiv.org/abs/1807.02313
  3. John Haslegrave, Joseph Hyde, Jaehoon Kim, Hong Liu, Ramsey numbers of cycles versus general graphs, Forum of Mathematics, Sigma 11 (2023), Paper No. e10, DOI 10.1017/fms.2023.6, arXiv:2112.03893, https://arxiv.org/abs/2112.03893
  4. Peter Allen, Graham Brightwell, Jozef Skokan, Ramsey-goodness—and otherwise, Combinatorica 33 (2013), 125–160, DOI 10.1007/s00493-013-2778-4, arXiv:1010.5079, https://arxiv.org/abs/1010.5079
  5. Richard Montgomery, Recent progress in graph theory using expansion, Proceedings of the International Congress of Mathematicians 2026, Vol. 6: Invited Lectures (Sections 12–14), SIAM (2026), 179–198, DOI 10.1137/25m1807915, arXiv:2607.26049, https://arxiv.org/abs/2607.26049
  6. S. A. Burr, Ramsey numbers involving graphs with long suspended paths, Journal of the London Mathematical Society (2) 24 (1981), 405–413, DOI 10.1112/jlms/s2-24.3.405
  7. P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, On cycle-complete graph Ramsey numbers, Journal of Graph Theory 2 (1978), 53–64, DOI 10.1002/jgt.3190020107
  8. V. Nikiforov, The Cycle-Complete Graph Ramsey Numbers, Combinatorics, Probability and Computing 14 (2005), 349–370, DOI 10.1017/S096354830400642X
  9. Peter Keevash, Eoin Long, Jozef Skokan, Cycle-Complete Ramsey Numbers, International Mathematics Research Notices (2021), 275–300, DOI 10.1093/imrn/rnz119
  10. J. A. Bondy, P. Erdős, Ramsey numbers for cycles in graphs, Journal of Combinatorial Theory, Series B 14 (1973), 46–54, DOI 10.1016/S0095-8956(73)80005-X
  11. Alexey Pokrovskiy, Benny Sudakov, Ramsey goodness of paths, Journal of Combinatorial Theory, Series B 122 (2017), 384–390, DOI 10.1016/j.jctb.2016.06.009
  12. Shaonan Mi, Ye Wang, Ramsey goodness of complete multipartite graphs with one large part, arXiv:2605.26826 (2026), https://arxiv.org/abs/2605.26826
  13. Abisek Dewan, Sayan Gupta, Rajiv Mishra, On Ramsey goodness of K2,nK_{2,n} versus cycles, arXiv:2605.06253 (2026), https://arxiv.org/abs/2605.06253