Browse › Combinatorics › 189 Cycle–clique Ramsey numbers
Cycle--clique Ramsey numbers
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that $R(C_m,K_n)=(m-1)(n-1)+1$ for every pair of integers $m\ge n\ge3$ other than $(m,n)=(3,3)$, for which $R(C_3,K_3)=6$. This establishes the cycle–clique conjecture of Erdős, Faudree, Rousseau and Schelp. The proof combines expansion in a minimal counterexample with a large-clique lemma and an optimization of paths joining clique vertices. These arguments reduce the remaining cases to $3{,}099$ finite parameter-pattern instances, which are excluded by two exact implementations of proved inference rules. Complete programs and deduction traces accompany the paper.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- anxkhn, bocowgill, mo271 (formal-conjectures contributors and reviewers), feat(ErdosProblems/551): record the full Ramsey formula (google-deepmind/formal-conjectures PR #6992, 8–11 October 2026, open as of 2026-10-21). The PR cites the paper's main theorem to mark
erdos_551as solved; reviewers discuss whether it covers the full parameter range and non-induced containment definitions and ask for a pinnedformal_prooflink with exactly matching statements, while the author notes the proof's axiom closure has not been checked.
Formalization
- OpenAI math release, Lean scope notes for family 189: Cycle–clique Ramsey numbers (lean/docs/189.md, 2026-10-06). The release's Lean formalization states $R(C_m,K_n)=(m-1)(n-1)+1$ for all $m\ge n\ge3$ except $(3,3)$, and $R(C_3,K_3)=6$, covering the paper's full main theorem; the comparator statement is in
CycleCliqueRamsey.lean. - Google DeepMind formal-conjectures, FormalConjectures/ErdosProblems/551.lean (formal-conjectures, accessed 2026-10-21). An independent Lean statement of the Erdős–Faudree–Rousseau–Schelp conjecture (Erdős Problem 551), still tagged
research openwithsorry, which also contains a "sufficiently large $n$" variant attributed to Keevash–Long–Skokan.
Possibly relevant literature (found by the agent, not checked)
- Cheng, Chen, Zhang, Ng, The Ramsey numbers for a cycle of length six or seven versus a clique of order seven (Discrete Math. 307 (2007) 1047–1053, doi:10.1016/j.disc.2006.07.036). Proves $R(C_7,K_7)=37$, the diagonal case of the $n=7$ range that the paper's introduction attributes to Chen–Cheng–Zhang (2008); not in the paper's bibliography.
- Radziszowski, Small Ramsey Numbers (Electron. J. Combin. Dynamic Survey DS1, revision #18, 2026-04-24). Section 4.2, "Cycles versus complete graphs," compiles known values and bounds of $R(C_m,K_n)$, relevant to the paper's account of earlier cases ($n\le7$ and $n=8$); not in the paper's bibliography.
Digests and expositions
- Latent Seminar, Exact cycle–clique Ramsey numbers (2026-10-07). Explains independent-set expansion, optimal path systems and the 3,099-pattern remainder, and states that it did not execute the finite checks, build Lean or verify manuscript-to-formal-statement equivalence.
- Gradient Damage, Circulant Hadamard Conjecture, Cycle–Clique Ramsey Numbers and 7 More in Combinatorics (video compilation, 2026-10-15). The chapter beginning at 1:02 introduces this paper's cycle–clique result; the accompanying page describes the animations as illustrations rather than proofs.
News and blogs
- Thomas Bloom (erdosproblems.com), Erdős problems in the OpenAI proofs (erdosproblems.com blog, 2026-10-08). The post has a section on Problem 551 that summarizes the paper's claimed result as the Erdős–Faudree–Rousseau–Schelp conjecture and notes that "This proof has been formalised."
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 189
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Cycle-clique-Ramsey-numbers-September-25-2026,
author = {{OpenAI}},
title = {{Cycle--clique Ramsey numbers}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf}{OAI:Cycle-clique-Ramsey-numbers-September-25-2026}},
year = {2026}
}From OpenAI's README for this paper:
Verification
The checker programs use only the Python 3 standard library. Use an ordinary Python 3 interpreter without optimization flags. From this directory, run both complete checkers and compare their output with the supplied data:
python3 verification/code/verify.py --output /tmp/cycle-clique-check
The wrapper retains the generated output and execution information in the specified directory. The supplied deduction traces are in verification/data/certificates.jsonl; they are not separate proof objects for an additional independent minimal validator.
Lean formalization
OpenAI provides Lean files for this family: lean/docs/189.md. The Lean statements have not been checked by people against the paper's claims.
Family 189: Cycle–clique Ramsey numbers
Proves the Erdős–Faudree–Rousseau–Schelp conjecture: $R(C_m,K_n)=(m-1)(n-1)+1$ for every $m\ge n\ge3$, except $R(C_3,K_3)=6$. This is the exact threshold forcing a red m-cycle or a blue n-clique in every red–blue coloring of a complete graph.
This is the only paper in this family.