Catalogue · Proof · Brute-force checks · Issue #146
Status: Elementary written proof, checked by brute force for . It settles Conjecture 2.1 of Johnson, Kaya and Matzke for every . 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 and a set , let be the chromatic number of the graph on in which two vertices are adjacent when their distance in lies in . The Babai -spectrum is the set of the values with . For the path with vertices , every and every ,
For the lower end is 2 and this is Theorem 2.2 of Johnson, Kaya and Matzke. For it is exactly their Conjecture 2.1. They proved the inclusion "" and left "" open.
The missing inclusion follows from a bound on independent sets. If is independent in the distance graph, the differences with are distinct elements of outside , so . Hence at least colours are needed. Greedy colouring gives the upper bound , and every value in between is attained by the construction of Johnson, Kaya and Matzke. The closed form covers both ranges of 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.pyThe script computes for every distance set with , 16,369 sets in all. It checks that the values for each form the interval of the theorem. It also checks the independence bound by exhaustive search for , and the integer of Johnson–Kaya–Matzke's Theorem 2.3 against the closed form. It takes a few seconds and prints one line per . An optional argument raises the bound on .
The theorem for general is proved in Lean. The Python script supplies an independent check in the stated finite range.
Files
PROOF.md: statement, lemmas, proof and sources.BabaiPathSpectrum.lean: the complete formalization.- Validation receipt: exact checked source/object hashes, commands, and local scope.
verify.py: standard-library brute-force check.