spectral_moore_max_order_mono
Sanity lemma: v(k, θ) is monotone in θ.
Statement
theorem spectral_moore_max_order_mono (k : ℕ) {θ θ' : ℝ} (h : θ ≤ θ') :
spectral_moore_max_order k θ ≤ spectral_moore_max_order k θ'- Source
- Sanity lemma for spectral_moore_max_order (arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), noted after Theorem 2.3: v(k, θ) ≤ v(k, ⌈θ⌉)).
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- spectral_moore_max_orderv(k, θ): the maximum number of vertices of a connected k-regular finite simple graph whose second largest adjacency eigenvalue is at most…
- spectral_moore_second_eigenvalue_leFor a finite simple graph G, the second largest adjacency eigenvalue is at most θ.
The proof, explained
The maximal order spectral_moore_max_order(k, θ) is defined as the supremum of the orders of all connected k-regular graphs whose second eigenvalue is at most θ. When θ ≤ θ', any graph meeting this spectral condition for θ also meets it for θ' by transitivity of ≤. Thus every admissible graph in the left-hand supremum is also an admissible witness for the right-hand supremum, so the supremum is monotone non-decreasing in θ.
To bound the supremum for θ by that for θ', it suffices to show that the order of any graph valid for θ is bounded by the supremum for θ'.
Unfolding the definition of spectral_moore_max_order expresses both sides as suprema over graph orders n, graphs G on n vertices, and proofs that G is connected, k-regular, and has second eigenvalue at most the parameter. By iSup₂_le and iSup_le, bounding the left-hand supremum by the right-hand side reduces to showing that for any fixed n, graph G on Fin n, and assumption hG that G satisfies the three conditions for θ, the order n is at most the supremum for θ'.
uses
iSup₂_le,iSup_leclassical unfold spectral_moore_max_order refine iSup₂_le fun n G => iSup_le fun hG => ?_
The order n is at most the right-hand supremum, provided G satisfies the second eigenvalue condition for θ'.
We bound n by instantiating the right-hand supremum at the exact same graph G on n vertices using le_iSup₂_of_le and le_iSup_of_le, observing that n ≤ n holds by reflexivity (le_rfl). The connectivity of G is provided directly by hG.1, and its k-regularity is supplied by hG.2.1, leaving only the verification of the eigenvalue condition for θ'.
uses
le_iSup₂_of_le,le_iSup_of_le,le_rflrefine le_iSup₂_of_le n G (le_iSup_of_le ⟨hG.1, ?_, ?_⟩ le_rfl) · convert hG.2.1The graph G satisfies the second eigenvalue bound for θ'.
For any eigenvalue index i > 0, the hypothesis hG.2.2 guarantees that the i-th eigenvalue of G is at most θ. Since θ ≤ θ' by assumption h, the eigenvalue is at most θ' by transitivity of ≤.
· intro i hi exact (hG.2.2 i hi).trans h
iSup₂_le- A double supremum ⨆ i, ⨆ j, f i j is bounded above by a if every term f i j is bounded above by a.
iSup_le- A supremum ⨆ i, f i is bounded above by a if every term f i is bounded above by a.
le_iSup₂_of_le- An element a is bounded above by a double supremum ⨆ i, ⨆ j, f i j if it is bounded above by any specific term f i j.
le_iSup_of_le- An element a is bounded above by a supremum ⨆ i, f i if it is bounded above by any specific term f i.
le_rfl- The inequality relation is reflexive: a ≤ a for every a.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem spectral_moore_max_order_mono (k : ℕ) {θ θ' : ℝ} (h : θ ≤ θ') : spectral_moore_max_order k θ ≤ spectral_moore_max_order k θ' := by classical unfold spectral_moore_max_order refine iSup₂_le fun n G => iSup_le fun hG => ?_ refine le_iSup₂_of_le n G (le_iSup_of_le ⟨hG.1, ?_, ?_⟩ le_rfl) · convert hG.2.1 · intro i hi exact (hG.2.2 i hi).trans h