AFTD Auto-Formalizing Theoretical Domains

spectral_extremal_chromatic_number

def

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

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
See it in the graphDiscuss this resultChallenge it