R(12,12)≥1661R(12,12) \ge 1661 by extending the Mathon–Shearer coloring

Yue Ma

Yue Ma reports a red–blue coloring of the edges of the complete graph on 1,660 vertices with no monochromatic clique of size 12. This gives R(12,12)≥1661R(12,12) \ge 1661.

What was already known

Ma’s earlier construction gave R(12,12)≥1658R(12,12) \ge 1658. Ma cites Miodrag Tatarević’s bound of 1641 as the best bound by other authors found in a literature search on 4 November.

AI involvement AI-led

Ma credits Claude Opus 5.5 with designing and running the search that produced the coloring and with writing the checking programs and Lean proof. Ma directed the project and revised the manuscript.

Importance Notable

The construction raises the lower bound by three through a new extension of the classical Mathon–Shearer coloring.

Technical verification Formal (Lean 4 + exact computation)

Ma reports Lean and NanoDa kernel checks of the coloring theorem. Two separately implemented exhaustive searches also found no monochromatic clique of size 12.

Formal checking

Ma reports Lean and NanoDa kernel checks of the coloring theorem. Two separately implemented exhaustive searches also found no monochromatic clique of size 12.

Checker
Lean and NanoDa as reported by Yue Ma
Scope
Yue Ma reports a red–blue coloring of the edges of the complete graph on 1,660 vertices with no monochromatic clique of size 12. This gives R(12,12)≥1661R(12,12) \ge 1661.
Basis
Reported by the linked checker

Human understanding Few

Ma directed the project and revised the paper. The disclosure reports partial human understanding without identifying which of the search ideas Ma can explain separately.

Correction and publication history