Johnson–Kaya–Matzke conjecture on Babai spectra of paths

What Lean checks

Lean proves the exact spectrum interval for every n ≥ 2 and 1 ≤ k < n, using the actual SimpleGraph.chromaticNumber of the distance graph on Fin n. It proves the independence and coloring bounds, greedy coloring, and modular-coloring/clique realization of every allowed value. Strict compilation, an all-owned audit of 43 declarations/39 theorem declarations and all 12 required endpoints, and stock-kernel replay passed. No published input remains a hypothesis. Local receipt; the combined repository gate and hosted validation remain separate.

Catalogue · Proof · Brute-force checks · Issue #146

Status: Elementary written proof, checked by brute force for n≤14n\le 14. It settles Conjecture 2.1 of Johnson, Kaya and Matzke for every nn. The note is unrefereed.

Lean status: complete for every n ≥ 2 and 1 ≤ k < n. BabaiPathSpectrum.spectrum_eq_interval proves both inclusions using the actual finite graph chromatic number. The construction of every allowed value is formalized without assuming the published realization theorem. Strict source compilation, an all-owned declaration/axiom audit, and independent stock-kernel replay passed. Local validation receipt. The combined repository gate and hosted validation are separate checks.

Primary source: P. Johnson, C. Kaya and R. W. Matzke, Babai numbers and Babai spectra of paths and cycles, arXiv:2409.04869, Conjecture 2.1.

Result

For a finite connected graph HH and a set D⊆{1,…,diamH}D\subseteq\{1,\dots,\mathop{\mathrm{diam}}H\}, let χ(H,D)\chi(H,D) be the chromatic number of the graph on V(H)V(H) in which two vertices are adjacent when their distance in HH lies in DD. The Babai kk-spectrum Spec(H,k)\mathop{\mathrm{Spec}}(H,k) is the set of the values χ(H,D)\chi(H,D) with |D|=k|D|=k. For the path PnP_n with vertices 1,…,n1,\dots,n, every n≥2n\ge 2 and every 1≤k≤n−11\le k\le n-1,

Spec(Pn,k)={⌈nn−k⌉,⌈nn−k⌉+1,…,k+1}.\mathop{\mathrm{Spec}}(P_n,k)=\Big\{\Big\lceil \frac{n}{n-k}\Big\rceil,\ \Big\lceil \frac{n}{n-k}\Big\rceil+1,\ \dots,\ k+1\Big\}.

For k≤n/2k\le n/2 the lower end is 2 and this is Theorem 2.2 of Johnson, Kaya and Matzke. For ⌊n/2⌋<k≤n−1\lfloor n/2\rfloor\lt k\le n-1 it is exactly their Conjecture 2.1. They proved the inclusion "⊇\supseteq" and left "⊆\subseteq" open.

The missing inclusion follows from a bound on independent sets. If SS is independent in the distance graph, the differences x−minSx-\min S with x∈S\{minS}x\in S\setminus\{\min S\} are |S|−1|S|-1 distinct elements of {1,…,n−1}\{1,\dots,n-1\} outside DD, so |S|≤n−k|S|\le n-k. Hence at least ⌈n/(n−k)⌉\lceil n/(n-k)\rceil colours are needed. Greedy colouring gives the upper bound k+1k+1, and every value in between is attained by the construction of Johnson, Kaya and Matzke. The closed form ⌈n/(n−k)⌉\lceil n/(n-k)\rceil covers both ranges of kk at once.

A literature search on 21 November 2026 found no later paper or arXiv version containing this argument.

Verification

Run from the repository root with Python 3.10 or later and no other dependencies:

python3 results/babai-spectrum-paths/verify.py

The script computes χ(Pn,D)\chi(P_n,D) for every distance set with 2≤n≤142\le n\le 14, 16,369 sets in all. It checks that the values for each (n,k)(n,k) form the interval of the theorem. It also checks the independence bound by exhaustive search for n≤10n\le 10, and the integer mm of Johnson–Kaya–Matzke's Theorem 2.3 against the closed form. It takes a few seconds and prints one line per nn. An optional argument raises the bound on nn.

The theorem for general nn is proved in Lean. The Python script supplies an independent check in the stated finite range.

Files