Family 189CombinatoricsNo LeanNot yet digested

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.

Manuscripts in this family · 1

Cycle--clique Ramsey numbers

Sep 25, 2026·Cycle-clique-Ramsey-numbers-September-25-2026.pdf

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.

Full abstract

PDF on GitHub LaTeX source