Search

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.

1 paper September 25, 2026 Explained by AI

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.

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.

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.

Many cases were settled one by one. The case n = 3 goes back to Chartrand and Schuster. Bondy and Erdős handled very long cycles, and later work completed the cases n = 4 through 7. In 2021, Keevash, Long and Skokan proved the formula for all large enough n. That left at most finitely many pairs open.

This paper proves the conjecture in full. 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. 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. A computer rules them out using proved rules. It searches patterns, not graphs or colourings. Two separate programs do this, with full records of each deduction.

The difficulty is that the cycle length is exact. 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

Lean notes

All quoted lines (11)
  1. For finite simple graphs HH and JJ, the Ramsey number R(H,J)R(H,J) is the least integer NN such that every red–blue colouring of the edges of the complete graph on NN vertices contains a red copy of HH or a blue copy of JJ.
    Cycle--clique Ramsey numbers Back to text
  2. Its lower bound comes from n−1n-1 disjoint red cliques of order m−1m-1, with all edges between them blue.
    Cycle--clique Ramsey numbers Back to text
  3. The case n=3n=3 goes back to Chartrand and Schuster; see also Bondy and Erd\Hos.
    Cycle--clique Ramsey numbers Back to text
  4. Bondy and Erd\Hos established the formula when m≥n2−2m\ge n^2-2. The complete conjectured range was established for n=4n=4 by Yang, Huang and Zhang, for n=5n=5 by Bollob\'as and coauthors, for n=6n=6 by Schiermeyer, and for n=7n=7 by Chen, Cheng and Zhang.
    Cycle--clique Ramsey numbers Back to text
  5. Thus their theorem leaves at most finitely many pairs in the range of Theorem ….
    Cycle--clique Ramsey numbers Back to text
  6. This establishes the cycle–clique conjecture of Erd\Hos, Faudree, Rousseau and Schelp.
    Cycle--clique Ramsey numbers Back to text
  7. The first structural step finds a clique of order t≥max⁡{3,⌊k/2⌋}.t\ge\max\{3,\lfloor k/2\rfloor\}.
    Cycle--clique Ramsey numbers Back to text
  8. There are 3,0993{,}099 parameter-pattern instances across the 4242 admissible pairs (k,t)(k,t).
    Cycle--clique Ramsey numbers Back to text
  9. The computation enumerates these patterns, rather than graphs or edge colourings.
    Cycle--clique Ramsey numbers Back to text
  10. Appendix … describes two separate exact implementations and the accompanying deduction traces.
    Cycle--clique Ramsey numbers Back to text
  11. The cycle length in the theorem is exact.
    Cycle--clique Ramsey numbers Back to text

Other sources

  1. openai/math, Lean scope note for family 189 (2026) This is the complete parameter range of the paper's main theorem.
  2. openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

Browse Combinatorics Erdős problemsRamsey theoryGraph theoryLean-checked results