spectral_extremal_chromatic_number
For an integer k ≥ 1 and real number r, the extremal distance-k chromatic number under spectral radius constraint r, denoted χ_λ(k, r), is the supremum of the chromatic number of the k-th power G^k over all finite simple graphs G with adjacency spectral radius at most r.
Statement
noncomputable def spectral_extremal_chromatic_number (k : ℕ) (r : ℝ) : ℕ∞
- Defined in
- arXiv:2610.13852 Section 6
- Verified
- 24 Oct 2026
- Axioms
- none listed
- Built on 2
- adjacency_spectral_radiusThe adjacency spectral radius of a simple graph G on a finite vertex set is the spectral radius of its real adjacency matrix.
- simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
- Used by 1
- spectral_extremal_clique_num_le_chromatic_numberFor every natural number k and real number r, the extremal distance-k clique number spectral_extremal_clique_num k r is less than or equal…
Read back from the Lean
Given a natural number $k$ and a real number $r$, spectral_extremal_chromatic_number k r is defined as the supremum in $\mathbb{N}_\infty$ (the extended natural numbers $\mathbb{N} \cup \{\infty\}$) over:
1. all natural numbers $n$,
2. all simple graphs $G$ on the vertex set $\mathrm{Fin}(n)$, and
3. the hypothesis that the adjacency spectral radius of $G$ is at most $\max(0, r)$ (represented as ENNReal.ofReal r),
of the chromatic number (in $\mathbb{N}_\infty$) of the $k$-th graph power of $G$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Extremal distance-k chromatic number under adjacency spectral radius constraint r. -/ noncomputable def spectral_extremal_chromatic_number (k : ℕ) (r : ℝ) : ℕ∞ := open scoped ENNReal in ⨆ (n : ℕ) (G : SimpleGraph (Fin n)) (_ : adjacency_spectral_radius G ≤ ENNReal.ofReal r), (simple_graph_power G k).chromaticNumber