AFTD Auto-Formalizing Theoretical Domains

spectral_extremal_clique_num

def

For an integer k ≥ 1 and real number r, the extremal distance-k clique number under spectral radius constraint r, denoted ω_λ(k, r), is the supremum of the clique 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_clique_num (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

The declaration spectral_extremal_clique_num defines a function taking a natural number k and a real number r and returning an extended natural number (ℕ∞). Its value is the supremum (in ℕ∞) over: 1. all natural numbers n : ℕ, 2. all simple graphs G on the vertex type Fin n, and 3. the hypothesis that the adjacency spectral radius of G is at most ENNReal.ofReal r, of the clique number of the $k$-th graph power of G (coerced to ℕ∞).

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 clique number under adjacency spectral radius constraint r. -/
noncomputable def spectral_extremal_clique_num (k : ℕ) (r : ℝ) : ℕ∞ := open scoped ENNReal in
  ⨆ (n : ℕ) (G : SimpleGraph (Fin n)) (_ : adjacency_spectral_radius G ≤ ENNReal.ofReal r),
    ((simple_graph_power G k).cliqueNum : ℕ∞)
See it in the graphDiscuss this resultChallenge it