Yue Ma

math.CO — Combinatorics

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

Contributed by Yue Ma

We prove that $R(12,12)\ge 1661$ by constructing a red/blue coloring of the edges of $K_{1660}$ with no monochromatic $K_{12}$. We start from a classical $(11,11)$-coloring on 1596 vertices, delete 21 of its vertices and add 85 new ones. Toward the remaining 1575 vertices, each new vertex has either the same colors as one of the deleted vertices or a single color. The deleted vertices include two pairs whose members have complementary colors toward every other vertex, and these pairs weaken the conditions that the new vertices must satisfy. The proof reduces to a finite check on the new vertices and is formally verified in Lean 4.

Author comments: 11 pages. The coloring, the check programs, the outputs of two exhaustive searches and the Lean 4 proof are at https://github.com/YueMa0/r1212-1661, archived as version 1.0.1 at https://doi.org/10.5281/zenodo.24087657.