# Cycle–clique Ramsey numbers > Exact Ramsey numbers for a cycle versus a clique: R(C_m, K_n) = (m − 1)(n − 1) + 1 when m ≥ n ≥ 3. Plain-English explainer, Lean status and sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-189/ Last updated: 2026-10-14 **Exact Ramsey numbers for a cycle versus a clique: R(C_m, K_n) = (m − 1)(n − 1) + 1 when m ≥ n ≥ 3.** **Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 25, 2026 · **Field:** Combinatorics · **Entry:** 189 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. Colour every line between N points red or blue. How large must N be to force either a red loop through exactly m points or a blue group of n points all joined? Erdős, Faudree, Rousseau and Schelp conjectured the answer (m − 1)(n − 1) + 1 in 1978. This paper proves it for every m ≥ n ≥ 3, apart from the known exception m = n = 3. ## At a glance - **First step:** — - **Significance:** Major. It settles a 1978 conjecture of Erdős and coauthors in its full stated range. - **Trust:** Formal proof listed - **Field:** Combinatorics (1 paper) ## The explanation Take six people and draw a line between every pair. Colour each line red or blue. Split the six into two groups of three. Colour lines inside each group red and lines between groups blue. Then no four people form a red loop, since each red cluster has only three people. And no three people are joined all in blue, since any three include two from the same group. Add a seventh person, and this escape is gone. Whatever colours you choose, you get a red loop through exactly four people or a blue triangle. The paper's formula gives exactly that seven. In the language of the subject, R(C₄, K₃) = 7. Here is the general setting. Join N points in every possible way and colour each line red or blue. A cycle C_m is a loop through exactly m points. A clique K_n is a set of n points all joined to each other. The Ramsey number R(C_m, K_n) is the smallest N that always forces a red C_m or a blue K_n[1]. In 1978, Erdős, Faudree, Rousseau and Schelp conjectured a formula. For m at least n at least 3, the answer should be (m − 1)(n − 1) + 1. The only exception is R(C₃, K₃) = 6. A red five-sided loop, with blue diagonals, shows why five points are not enough there. The lower bound comes from the opening picture, scaled up: n − 1 red clusters of m − 1 points, with blue lines between[2]. Many cases were settled one by one. The case n = 3 goes back to Chartrand and Schuster[3]. Bondy and Erdős handled very long cycles, and later work completed the cases n = 4 through 7[4]. In 2021, Keevash, Long and Skokan proved the formula for all large enough n. That left at most finitely many pairs open[5]. This paper proves the conjecture in full[6]. It does not need the size of the unknown constant from the 2021 result. It studies a smallest failing case and first finds a large clique inside it[7]. Then it grows paths between clique points and shows that certain improvements would close a loop of exactly the right length. The last small cases come down to 3,099 finite patterns across 42 parameter pairs[8]. A computer rules them out using proved rules. It searches patterns, not graphs or colourings[9]. Two separate programs do this, with full records of each deduction[10]. The difficulty is that the cycle length is exact[11]. A loop through more or fewer than m points does not count. That is why the paper tracks paths so carefully. How sure is this? A computer proof checker called Lean has checked a formal version of the theorem. The Lean scope note says it covers every m at least n at least 3, plus the exception R(C₃, K₃) = 6. That is the paper's full range. No specialist review of the paper has been published. **What it doesn't show.** This does not cover cycles shorter than the clique size, where m is less than n. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major if it holds. Lean has checked the full theorem; part of the paper's own proof uses computer checks of finite patterns, and no specialist review is published. ## Words used - **Ramsey number:** The smallest number of points that forces a given red shape or blue shape in every red–blue colouring. - **Cycle:** A closed loop through a set of points, each visited once. - **Clique:** A set of points with every pair joined. - **Complete graph:** A set of points with every pair joined by a line. - **Colouring:** An assignment of red or blue to each line. ## The original paper - [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf) - September 25, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/189.md) ## Quoted lines from the paper (11) [1] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > For finite simple graphs $H$ and $J$, the Ramsey number $R(H,J)$ is the least integer $N$ such that every red--blue colouring of the edges of the complete graph on $N$ vertices contains a red copy of $H$ or a blue copy of $J$. [2] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > Its lower bound comes from $n-1$ disjoint red cliques of order $m-1$, with all edges between them blue. [3] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > The case $n=3$ goes back to Chartrand and Schuster; see also Bondy and Erd\H{o}s. [4] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > Bondy and Erd\H{o}s established the formula when $m\ge n^2-2$. The complete conjectured range was established for $n=4$ by Yang, Huang and Zhang, for $n=5$ by Bollob\'as and coauthors, for $n=6$ by Schiermeyer, and for $n=7$ by Chen, Cheng and Zhang. [5] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > Thus their theorem leaves at most finitely many pairs in the range of Theorem …. [6] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > This establishes the cycle--clique conjecture of Erd\H{o}s, Faudree, Rousseau and Schelp. [7] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > The first structural step finds a clique of order \[ t\ge\max\{3,\lfloor k/2\rfloor\}. \] [8] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > There are $3{,}099$ parameter-pattern instances across the $42$ admissible pairs $(k,t)$. [9] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > The computation enumerates these patterns, rather than graphs or edge colourings. [10] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > Appendix … describes two separate exact implementations and the accompanying deduction traces. [11] From [Cycle--clique Ramsey numbers](https://github.com/openai/math/blob/main/preprints/Cycle-clique-Ramsey-numbers-September-25-2026/Cycle-clique-Ramsey-numbers-September-25-2026.pdf): > The cycle length in the theorem is exact. ## Other sources - [openai/math, Lean scope note for family 189 (2026)](https://github.com/openai/math/blob/main/lean/docs/189.md): “This is the complete parameter range of the paper's main theorem.” - [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” ## Related - [The hypercube Ramsey conjecture](https://closedform.nishachay.tech/e/openai-math-2026-171/) - Combinatorics - [Superexponential van der Waerden numbers](https://closedform.nishachay.tech/e/openai-math-2026-160/) - Combinatorics - [Correspondence coloring with a fixed forbidden subgraph](https://closedform.nishachay.tech/e/openai-math-2026-184/) - Combinatorics - [The Erdős–Gallai cycle-decomposition conjecture](https://closedform.nishachay.tech/e/openai-math-2026-181/) - Combinatorics - [Classification of finite Euclidean Ramsey configurations](https://closedform.nishachay.tech/e/openai-math-2026-172/) - Combinatorics - [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 37 results - [Erdős problems](https://closedform.nishachay.tech/topic/erdos-problems/) - Topic · 13 results - [Ramsey theory](https://closedform.nishachay.tech/topic/ramsey-theory/) - Topic · 5 results - [Graph theory](https://closedform.nishachay.tech/topic/graph-theory/) - Topic · 40 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20189%5D%20)