Status: complete written proof and Lean formalization for every admissible n,k. Strict compilation, an all-owned declaration/axiom audit, and stock-kernel replay passed; local receipt. The additional brute-force check covers .
Statement
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
Take the path with vertices , so that the distance is and the diameter is . [JKM, Definitions 1.1 and 1.2]
Theorem. For all integers and ,
For the lower end is 2, and the statement is [JKM, Theorem 2.2]. For the lower end equals , where is the integer of [JKM, Theorem 2.3] (Lemma 4 below), so the statement is exactly Conjecture 2.1 of Johnson, Kaya and Matzke. They proved the inclusion "" and left "" open.
Proof
Write for the graph on with when , and let .
Lemma 1 (independent sets). Every independent set of has .
Proof. Let . The numbers for are distinct elements of , and none of them lies in . So . ∎
Lemma 2 (lower bound). .
Proof. The colour classes are independent, so by Lemma 1 a proper colouring with colours covers at most vertices. ∎
Lemma 3 (upper bound). . [JKM, Theorem 2.1]
Proof. Colour in this order. A vertex has at most neighbours among the earlier vertices, namely the with , so one of colours is free. ∎
Lemma 4 (the integer of the conjecture). Let and let be an integer with . Then .
Proof. The right inequality gives , so . The left one gives , so and . ∎
Lemma 5 (every value occurs). Let . Then there is a set with and .
Proof. This is the construction used in [JKM, proofs of Theorems 2.2 and 2.3]. The number of multiples of in is . Since , we have , so there are at most such multiples and at least integers in that are not divisible by . Because , we can choose of size consisting of and further integers not divisible by . Then is a proper colouring of , as no element of is divisible by . The vertices are pairwise adjacent, as their differences lie in , and . So . ∎
Proof of the Theorem. Lemmas 2 and 3 give "" and Lemma 5 gives "". ∎
Remark (the bounds of Lemmas 1 and 2 are attained by one explicit set). For the set is independent, and the colouring is proper with colours.
What is new
- The inclusion "" for , that is Lemmas 1 and 2. With [JKM, Theorem 2.3] this settles Conjecture 2.1.
- The closed form for the lower end, which covers both ranges of at once.
The argument is short. We found no later paper or later arXiv version that contains it (searched 21 November 2026).
Verification
python3 verify.py 14 computes for every with (16,369 distance sets) and checks that the set of values for each is the interval of the Theorem. It also checks Lemma 1 by exhaustive search for and Lemma 4 against the definition of in the paper. Standard library only; it takes a few seconds.
Sources
- [JKM] P. Johnson, C. Kaya and R. W. Matzke, Babai numbers and Babai spectra of paths and cycles, arXiv:2409.04869 (August 2024). Definitions 1.1 and 1.2, Theorems 2.1 to 2.3, Conjecture 2.1.