Mustafa Stanikzai

math.CO — Combinatorics

The independence number of the generalized Johnson graph $J(13,5,3)$

Contributed by Mustafa Stanikzai

Let $J(13,5,3)$ be the graph on the 5-element subsets of a 13-element set, two subsets being adjacent when they share exactly 3 elements. We prove that $\alpha(J(13,5,3)) = 33$. The graph is an explicit unit-distance graph in $\mathbb{R}^{12}$, so $\chi(\mathbb{R}^{12}) \ge \lceil 1287/33 \rceil = 39$; earlier bounds from explicit finite graphs give at most 38. A recent preprint of Davies gives much larger bounds, none from an explicit finite graph. An explicit independent set gives $\alpha \ge 33$. For the upper bound, a symmetry reduction splits the problem into 200 clique subproblems, and a certifying solver refutes each one with a proof log that the checker VeriPB accepts. An uncertified computation reproduces the value $\alpha(J(13,6,4)) = 46$ reported by Exoo and Ismailescu, which gives $\chi(\mathbb{R}^{12}) \ge 38$.

Author comments: 16 pages. Programs, certificates and proof logs: https://doi.org/10.5281/zenodo.24145863