AFTD Auto-Formalizing Theoretical Domains

spectral_moore_max_order

def

v(k, θ): the maximum number of vertices of a connected k-regular finite simple graph whose second largest adjacency eigenvalue is at most θ, as an extended natural number (⊤ when there are such graphs of every large order).

Statement

noncomputable def spectral_moore_max_order (k : ℕ) (θ : ℝ) : ℕ∞
Defined in
arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), Sec. 1 (definition of v(k, θ)); infinite values allowed, as in the paper's remark that v(k, θ) is infinite for θ ≥ 2√(k−1).
Verified
07 Nov 2026
Axioms
none listed
Built on 1
Used by 5

Read back from the Lean

spectral_moore_max_order is a function taking a degree k : ℕ and a real threshold θ : ℝ, returning an extended natural number in ℕ∞ (i.e. WithTop ℕ). It is defined as the supremum in ℕ∞ of n : ℕ∞ over all n : ℕ for which there exists a simple graph G on Fin n such that: 1. G is connected (G.Connected); 2. G is regular of degree k (G.IsRegularOfDegree k); and 3. G satisfies spectral_moore_second_eigenvalue_le 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

/-- `v(k, θ)`: the maximum order of a connected `k`-regular simple graph whose second largest adjacency eigenvalue is at most `θ` (`⊤` when the orders are unbounded). -/
noncomputable def spectral_moore_max_order (k : ℕ) (θ : ℝ) : ℕ∞ := open Classical in
  ⨆ (n : ℕ) (G : SimpleGraph (Fin n))
    (_ : G.Connected ∧ G.IsRegularOfDegree k ∧ spectral_moore_second_eigenvalue_le G θ), (n : ℕ∞)
See it in the graphDiscuss this resultChallenge it