The Babai k-spectrum of a path (Johnson–Kaya–Matzke, Conjecture 2.1)

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.

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 n≤14n\le 14.

Statement

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 is

Spec(H,k)={χ(H,D):D⊆{1,…,diamH},|D|=k}.\mathop{\mathrm{Spec}}(H,k)=\{\chi(H,D): D\subseteq\{1,\dots,\mathop{\mathrm{diam}}H\},\ |D|=k\}.

Take the path PnP_n with vertices 1,…,n1,\dots,n, so that the distance is |u−v||u-v| and the diameter is n−1n-1. [JKM, Definitions 1.1 and 1.2]

Theorem. For all integers n≥2n\ge 2 and 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 the statement is [JKM, Theorem 2.2]. For ⌊n/2⌋<k≤n−1\lfloor n/2\rfloor\lt k\le n-1 the lower end equals m+1m+1, where mm 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 "⊇\supseteq" and left "⊆\subseteq" open.

Proof

Write GDG_D for the graph on {1,…,n}\{1,\dots,n\} with u∼vu\sim v when |u−v|∈D|u-v|\in D, and let |D|=k|D|=k.

Lemma 1 (independent sets). Every independent set SS of GDG_D has |S|≤n−k|S|\le n-k.

Proof. Let a=minSa=\min S. The numbers x−ax-a for x∈S\{a}x\in S\setminus\{a\} are |S|−1|S|-1 distinct elements of {1,…,n−1}\{1,\dots,n-1\}, and none of them lies in DD. So |S|−1≤(n−1)−k|S|-1\le (n-1)-k. ∎

Lemma 2 (lower bound). χ(Pn,D)≥⌈n/(n−k)⌉\chi(P_n,D)\ge\lceil n/(n-k)\rceil.

Proof. The colour classes are independent, so by Lemma 1 a proper colouring with cc colours covers at most c(n−k)c(n-k) vertices. ∎

Lemma 3 (upper bound). χ(Pn,D)≤k+1\chi(P_n,D)\le k+1. [JKM, Theorem 2.1]

Proof. Colour 1,2,…,n1,2,\dots,n in this order. A vertex vv has at most kk neighbours among the earlier vertices, namely the v−dv-d with d∈Dd\in D, so one of k+1k+1 colours is free. ∎

Lemma 4 (the integer mm of the conjecture). Let ⌊n/2⌋<k≤n−1\lfloor n/2\rfloor\lt k\le n-1 and let mm be an integer with n−⌈n/m⌉<k≤n−⌈n/(m+1)⌉n-\lceil n/m\rceil\lt k\le n-\lceil n/(m+1)\rceil. Then ⌈n/(n−k)⌉=m+1\lceil n/(n-k)\rceil=m+1.

Proof. The right inequality gives n−k≥n/(m+1)n-k\ge n/(m+1), so n/(n−k)≤m+1n/(n-k)\le m+1. The left one gives n−k<⌈n/m⌉n-k\lt\lceil n/m\rceil, so n−k≤⌈n/m⌉−1<n/mn-k\le\lceil n/m\rceil-1\lt n/m and n/(n−k)>mn/(n-k)\gt m. ∎

Lemma 5 (every value occurs). Let ⌈n/(n−k)⌉≤s≤k+1\lceil n/(n-k)\rceil\le s\le k+1. Then there is a set DD with |D|=k|D|=k and χ(Pn,D)=s\chi(P_n,D)=s.

Proof. This is the construction used in [JKM, proofs of Theorems 2.2 and 2.3]. The number of multiples of ss in {1,…,n−1}\{1,\dots,n-1\} is ⌊(n−1)/s⌋\lfloor (n-1)/s\rfloor. Since s≥n/(n−k)s\ge n/(n-k), we have (n−1)/s≤(n−1)(n−k)/n<n−k(n-1)/s\le (n-1)(n-k)/n\lt n-k, so there are at most n−k−1n-k-1 such multiples and at least kk integers in {1,…,n−1}\{1,\dots,n-1\} that are not divisible by ss. Because s−1≤ks-1\le k, we can choose DD of size kk consisting of 1,…,s−11,\dots,s-1 and k−s+1k-s+1 further integers not divisible by ss. Then v↦vmodsv\mapsto v \bmod s is a proper colouring of GDG_D, as no element of DD is divisible by ss. The vertices 1,…,s1,\dots,s are pairwise adjacent, as their differences lie in {1,…,s−1}⊆D\{1,\dots,s-1\}\subseteq D, and s≤k+1≤ns\le k+1\le n. So χ(Pn,D)=s\chi(P_n,D)=s. ∎

Proof of the Theorem. Lemmas 2 and 3 give "⊆\subseteq" and Lemma 5 gives "⊇\supseteq". ∎

Remark (the bounds of Lemmas 1 and 2 are attained by one explicit set). For D={n−k,…,n−1}D=\{n-k,\dots,n-1\} the set {1,…,n−k}\{1,\dots,n-k\} is independent, and the colouring v↦⌈v/(n−k)⌉v\mapsto\lceil v/(n-k)\rceil is proper with ⌈n/(n−k)⌉\lceil n/(n-k)\rceil colours.

What is new

  • The inclusion "⊆\subseteq" for k>n/2k\gt n/2, that is Lemmas 1 and 2. With [JKM, Theorem 2.3] this settles Conjecture 2.1.
  • The closed form ⌈n/(n−k)⌉\lceil n/(n-k)\rceil for the lower end, which covers both ranges of kk 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 χ(Pn,D)\chi(P_n,D) for every DD with 2≤n≤142\le n\le 14 (16,369 distance sets) and checks that the set of values for each (n,k)(n,k) is the interval of the Theorem. It also checks Lemma 1 by exhaustive search for n≤10n\le 10 and Lemma 4 against the definition of mm 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.