Erdős Problem #551 — Cycle-versus-clique Ramsey numbers
For graphs and , let be the least integer such that every red/blue coloring of the edges of the complete graph on vertices contains either a red copy of or a blue copy of . Write for a cycle of length and for the complete graph on vertices. The Erdős–Faudree–Rousseau–Schelp conjecture asks whether, for every pair of integers other than , Erdős Problem #551 Keevash, Long, and Skokan (2021)
Erdős Problem #551 Keevash, Long, and Skokan (2021)
Background
The expression on the right is the general Chvátal–Harary lower bound for a connected graph versus a clique. For cycles, take disjoint red cliques of order and color every edge between them blue. There is no red -cycle, and a blue clique can use at most one vertex from each red clique, so this coloring has vertices without either target. The conjecture is therefore an equality question: can every coloring on one more vertex be forced to contain one of the two graphs? Keevash, Long, and Skokan (2021)
Erdős, Faudree, Rousseau, and Schelp proposed the cycle identity in 1978 and also asked how its threshold in depends on fixed , and which cycle length minimizes . Bondy and Erdős proved equality for ; Schiermeyer improved this range, and Nikiforov later proved equality for . The exceptional pair is excluded from the conjectured identity. Erdős, Faudree, Rousseau, and Schelp (1978) Erdős Problem #551 Keevash, Long, and Skokan (2021)
References
P. Keevash, E. Long, and J. Skokan, Cycle-complete Ramsey numbers, International Mathematics Research Notices 2021 (2021), 277–300.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
Claimed by OpenAI. Claims that R(Cm , Kn ) = (m−1)(n−1)+1 for every pair of integers m ≥ n ≥ 3 other than (m, n) = (3, 3), for which R(C3 , K3 ) = 6. This establishes the cycle–clique conjecture of Erdős, Faudree, Rousseau and Schelp.See full solution
Claimed by OpenAI.
Claims that R(Cm , Kn ) = (m−1)(n−1)+1 for every pair of integers m ≥ n ≥ 3 other than (m, n) = (3, 3), for which R(C3 , K3 ) = 6. This establishes the cycle–clique conjecture of Erdős, Faudree, Rousseau and Schelp.
GitHub repository: https://github.com/openai/math
- OpenAI-189-01-Cycle-clique-Ramsey-numbers.pdfOpen