← All problems

Erdős Problem #551 — Cycle-versus-clique Ramsey numbers

48 years old · traced to

For graphs XX and YY, let R(X,Y)R(X,Y) be the least integer NN such that every red/blue coloring of the edges of the complete graph on NN vertices contains either a red copy of XX or a blue copy of YY. Write CkC_k for a cycle of length kk and KnK_n for the complete graph on nn vertices. The Erdős–Faudree–Rousseau–Schelp conjecture asks whether, for every pair of integers k≥n≥3k\ge n\ge3 other than (k,n)=(3,3)(k,n)=(3,3), Erdős Problem #551 Keevash, Long, and Skokan (2021)

R(Ck,Kn)=(k−1)(n−1)+1.R(C_k,K_n)=(k-1)(n-1)+1.

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 (n−1)(n-1) disjoint red cliques of order k−1k-1 and color every edge between them blue. There is no red kk-cycle, and a blue clique can use at most one vertex from each red clique, so this coloring has (k−1)(n−1)(k-1)(n-1) 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 kk depends on fixed nn, and which cycle length minimizes R(Ck,Kn)R(C_k,K_n). Bondy and Erdős proved equality for k≥n2−2k\ge n^2-2; Schiermeyer improved this range, and Nikiforov later proved equality for k≥4n+2k\ge4n+2. The exceptional pair (3,3)(3,3) 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.

Source: P. Keevash, E. Long, and J. Skokan, Cycle-complete Ramsey numbers, International Mathematics Research Notices 2021 (2021), 277–300.

Progress summary

Never refreshed

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 solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf

  • OpenAI-189-01-Cycle-clique-Ramsey-numbers.pdf611,068 bytesOpen