spectral_moore_max_order
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
- spectral_moore_second_eigenvalue_leFor a finite simple graph G, the second largest adjacency eigenvalue is at most θ.
- Used by 5
- spectral_moore_max_order_monoSanity lemma: v(k, θ) is monotone in θ.
- spectral_moore_degree_thresholdK(θ): the least natural number K such that v(k, θ) ≤ 2k + 2⌊1 + θ²/4⌋ for every degree k ≥ K (defaulting to 0 if there is no such K).
- spectral_moore_max_order_le_of_large_degree_of_switch_degree_boundsLet θ ≥ 1. Suppose (i) there are D, N₀ such that every k-regular graph G on Fin n with second largest adjacency eigenvalue at most θ, 2k +…
- spectral_moore_degree_threshold_specSanity lemma: if some degree threshold exists, the bound v(k, θ) ≤ 2k + 2⌊1 + θ²/4⌋ holds for every k ≥ K(θ).
- spectral_moore_degree_threshold_leSanity lemma: K(θ) is at most every degree from which the bound holds.
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 : ℕ∞)