spectral_moore_seidel_switch_adj_quadform_le
Let G be a k-regular finite simple graph on V with second largest adjacency eigenvalue at most θ and k ≤ θ + |V|/2. Then for every X : Set V, the Seidel switching F = spectral_moore_seidel_switch G X satisfies x ⬝ᵥ (F.adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x) for every x : V → ℝ with ∑ v, x v = 0.
Statement
open Classical SimpleGraph Matrix in theorem spectral_moore_seidel_switch_adj_quadform_le {V : Type*} [Fintype V] (G : SimpleGraph V) (X : Set V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k) (hθ : spectral_moore_second_eigenvalue_le G θ) (hk : (k : ℝ) ≤ θ + (Fintype.card V : ℝ) / 2) (x : V → ℝ) (hx : ∑ v, x v = 0) : x ⬝ᵥ ((spectral_moore_seidel_switch G X).adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x)
- Source
- arXiv:2611.00591 (A spectral Moore problem and the Yang-Koolen conjecture), Section 5, Lemma 5.1, inequality (12)
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- spectral_moore_seidel_switchSeidel switching: for a simple graph G : SimpleGraph V and a set X : Set V, the simple graph on V in which distinct vertices u, v are…
- spectral_moore_adj_quadform_le_add_sum_sqFor a k-regular finite simple graph G on a vertex type V with second largest adjacency eigenvalue at most θ and k ≤ θ + |V|/2, every x : V…
- spectral_moore_second_eigenvalue_leFor a finite simple graph G, the second largest adjacency eigenvalue is at most θ.
- Used by 1
- 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 +…
The proof, explained
The proof encodes the subset X as a sign function s : V → {±1} and observes that the adjacency matrix of the Seidel switched graph F satisfies A_F(u, v) = (1 - s(u)s(v))/2 + s(u)s(v) A_G(u, v). Substituting the signed vector y(v) = s(v) x(v) into this formula decomposes x ⬝ᵥ (A_F *ᵥ x) into (∑ v, x v)^2 / 2 - (∑ v, y v)^2 / 2 + y ⬝ᵥ (A_G *ᵥ y). Since ∑ v, x v = 0 and y ⬝ᵥ y = x ⬝ᵥ x, the bound y ⬝ᵥ (A_G *ᵥ y) ≤ θ (y ⬝ᵥ y) + (∑ v, y v)^2 / 2 cancels the remaining squared sum, establishing x ⬝ᵥ (A_F *ᵥ x) ≤ θ (x ⬝ᵥ x).
Define the sign vector s : V → ℝ with s(v) = 1 for v ∈ X and -1 for v ∉ X, and observe s(v)^2 = 1 for all v.
We assign s(v) = 1 if v ∈ X and -1 otherwise. In both cases, s(v)^2 = 1, as verified by case analysis on whether v ∈ X.
set s : V → ℝ := fun v => if v ∈ X then 1 else -1 with hs have hs2 : ∀ v, s v * s v = 1 := by intro v; simp only [hs]; split_ifs <;> norm_num
For all u, v ∈ V, the adjacency matrix of the Seidel switched graph satisfies A_F(u, v) = (1 - s(u)s(v))/2 + s(u)s(v) A_G(u, v).
If u = v, both sides vanish since simple graphs have no loops and 1 - s(u)^2 = 0. If u ≠ v, by definition of Seidel switching, u and v are adjacent in F if and only if their adjacency in G is toggled when exactly one of u, v belongs to X. Since s(u)s(v) = 1 when u and v are either both in X or both outside X, and s(u)s(v) = -1 otherwise, this algebraic formula reproduces the adjacency condition in all cases.
uses
adjMatrix_applyhave hentry : ∀ u v, (spectral_moore_seidel_switch G X).adjMatrix ℝ u v = (1 - s u * s v) / 2 + s u * s v * G.adjMatrix ℝ u v := by intro u v by_cases huv : u = v · subst huv; simp [hs2] have hadj : (spectral_moore_seidel_switch G X).Adj u v ↔ (G.Adj u v ↔ (u ∈ X ↔ v ∈ X)) := by change u ≠ v ∧ _ ↔ _ simp [huv] rw [adjMatrix_apply, adjMatrix_apply] simp only [hs] by_cases hu : u ∈ X <;> by_cases hv : v ∈ X <;> by_cases hG : G.Adj u v <;> simp [hu, hv, hG, hadj]
For y(v) = s(v) x(v), we have y ⬝ᵥ y = x ⬝ᵥ x and y ⬝ᵥ (A_G *ᵥ y) ≤ θ (y ⬝ᵥ y) + (∑ v, y v)^2 / 2.
The quadratic form bound on G applies directly to y via spectral_moore_adj_quadform_le_add_sum_sq. Moreover, since s(v)^2 = 1 for each vertex v, each summand satisfies y(v)^2 = s(v)^2 x(v)^2 = x(v)^2, so y ⬝ᵥ y = x ⬝ᵥ x.
uses
spectral_moore_adj_quadform_le_add_sum_sq,Finset.sum_congr,one_mulset y : V → ℝ := fun v => s v * x v with hy have hq := spectral_moore_adj_quadform_le_add_sum_sq G k θ hreg hθ hk y have hyy : y ⬝ᵥ y = x ⬝ᵥ x := by simp only [dotProduct, hy] exact Finset.sum_congr rfl fun v _ => by calc s v * x v * (s v * x v) = (s v * s v) * (x v * x v) := by ring _ = x v * x v := by rw [hs2, one_mul]
The switched quadratic form expands as x ⬝ᵥ (A_F *ᵥ x) = (∑ v, x v)^2 / 2 - (∑ v, y v)^2 / 2 + y ⬝ᵥ (A_G *ᵥ y).
Expressing quadratic forms and squared sums as double sums over u, v ∈ V and substituting the entry formula A_F(u, v) = (1 - s(u)s(v))/2 + s(u)s(v) A_G(u, v), the expression splits into (1/2) ∑_{u,v} x(u) x(v) = (∑ v, x v)^2 / 2, minus (1/2) ∑_{u,v} (s(u)x(u))(s(v)x(v)) = (∑ v, y v)^2 / 2, plus ∑_{u,v} y(u) A_G(u, v) y(v) = y ⬝ᵥ (A_G *ᵥ y).
uses
Finset.mul_sum,mul_assoc,sq,Finset.sum_mul_sum,Finset.sum_div,Finset.sum_sub_distrib,Finset.sum_add_distrib,Finset.sum_congrhave e : x ⬝ᵥ ((spectral_moore_seidel_switch G X).adjMatrix ℝ *ᵥ x) = (∑ v, x v) ^ 2 / 2 - (∑ v, y v) ^ 2 / 2 + y ⬝ᵥ (G.adjMatrix ℝ *ᵥ y) := by have L : ∀ (M : Matrix V V ℝ) (w : V → ℝ), w ⬝ᵥ (M *ᵥ w) = ∑ u, ∑ v, w u * M u v * w v := by intro M w simp only [dotProduct, mulVec, Finset.mul_sum, mul_assoc] have R : ∀ w : V → ℝ, (∑ v, w v) ^ 2 = ∑ u, ∑ v, w u * w v := by intro w; rw [sq, Finset.sum_mul_sum] rw [L, L, R, R, Finset.sum_div, Finset.sum_div, ← Finset.sum_sub_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun u _ => ?_ rw [Finset.sum_div, Finset.sum_div, ← Finset.sum_sub_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun v _ => ?_ rw [hentry]; simp only [hy]; ring
The bound x ⬝ᵥ (A_F *ᵥ x) ≤ θ (x ⬝ᵥ x) holds.
Since ∑ v, x v = 0, the first term vanishes, leaving x ⬝ᵥ (A_F *ᵥ x) = -(∑ v, y v)^2 / 2 + y ⬝ᵥ (A_G *ᵥ y). Substituting the bound on y ⬝ᵥ (A_G *ᵥ y) and using y ⬝ᵥ y = x ⬝ᵥ x, the terms +(∑ v, y v)^2 / 2 and -(∑ v, y v)^2 / 2 cancel out, giving the result.
uses
sq_nonnegrw [e, hx, ← hyy] nlinarith [sq_nonneg (∑ v, y v)]
adjMatrix_apply- The (u, v)-entry of the adjacency matrix of a simple graph is 1 if u and v are adjacent and 0 otherwise.
spectral_moore_adj_quadform_le_add_sum_sq- For a k-regular graph with second adjacency eigenvalue at most θ and k ≤ θ + |V|/2, the quadratic form x ⬝ᵥ (A *ᵥ x) is at most θ (x ⬝ᵥ x) + (∑ v, x v)^2 / 2 for every vector x.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
one_mul- 1 * a = a for any element a of a multiplicative structure with 1.
Finset.mul_sum- Scalar multiplication distributes over finite sums: a * ∑ i, f i = ∑ i, a * f i.
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
sq- The square of an element equals the element multiplied by itself: a ^ 2 = a * a.
Finset.sum_mul_sum- The product of two finite sums equals the double sum of their pointwise products: (∑ i, f i) * (∑ j, g j) = ∑ i, ∑ j, f i * g j.
Finset.sum_div- Dividing a finite sum by a scalar equals the sum of each term divided by that scalar: (∑ i, f i) / a = ∑ i, (f i / a).
Finset.sum_sub_distrib- The sum of differences over a finite set equals the difference of the respective sums: ∑ i, (f i - g i) = (∑ i, f i) - (∑ i, g i).
Finset.sum_add_distrib- The sum of sums over a finite set equals the sum of the respective sums: ∑ i, (f i + g i) = (∑ i, f i) + (∑ i, g i).
sq_nonneg- The square of any real number is non-negative: 0 ≤ a ^ 2.
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.
open Classical SimpleGraph Matrix intheorem spectral_moore_seidel_switch_adj_quadform_le {V : Type*} [Fintype V] (G : SimpleGraph V) (X : Set V) (k : ℕ) (θ : ℝ) (hreg : G.IsRegularOfDegree k) (hθ : spectral_moore_second_eigenvalue_le G θ) (hk : (k : ℝ) ≤ θ + (Fintype.card V : ℝ) / 2) (x : V → ℝ) (hx : ∑ v, x v = 0) : x ⬝ᵥ ((spectral_moore_seidel_switch G X).adjMatrix ℝ *ᵥ x) ≤ θ * (x ⬝ᵥ x) := by set s : V → ℝ := fun v => if v ∈ X then 1 else -1 with hs have hs2 : ∀ v, s v * s v = 1 := by intro v; simp only [hs]; split_ifs <;> norm_num have hentry : ∀ u v, (spectral_moore_seidel_switch G X).adjMatrix ℝ u v = (1 - s u * s v) / 2 + s u * s v * G.adjMatrix ℝ u v := by intro u v by_cases huv : u = v · subst huv; simp [hs2] have hadj : (spectral_moore_seidel_switch G X).Adj u v ↔ (G.Adj u v ↔ (u ∈ X ↔ v ∈ X)) := by change u ≠ v ∧ _ ↔ _ simp [huv] rw [adjMatrix_apply, adjMatrix_apply] simp only [hs] by_cases hu : u ∈ X <;> by_cases hv : v ∈ X <;> by_cases hG : G.Adj u v <;> simp [hu, hv, hG, hadj] set y : V → ℝ := fun v => s v * x v with hy have hq := spectral_moore_adj_quadform_le_add_sum_sq G k θ hreg hθ hk y have hyy : y ⬝ᵥ y = x ⬝ᵥ x := by simp only [dotProduct, hy] exact Finset.sum_congr rfl fun v _ => by calc s v * x v * (s v * x v) = (s v * s v) * (x v * x v) := by ring _ = x v * x v := by rw [hs2, one_mul] have e : x ⬝ᵥ ((spectral_moore_seidel_switch G X).adjMatrix ℝ *ᵥ x) = (∑ v, x v) ^ 2 / 2 - (∑ v, y v) ^ 2 / 2 + y ⬝ᵥ (G.adjMatrix ℝ *ᵥ y) := by have L : ∀ (M : Matrix V V ℝ) (w : V → ℝ), w ⬝ᵥ (M *ᵥ w) = ∑ u, ∑ v, w u * M u v * w v := by intro M w simp only [dotProduct, mulVec, Finset.mul_sum, mul_assoc] have R : ∀ w : V → ℝ, (∑ v, w v) ^ 2 = ∑ u, ∑ v, w u * w v := by intro w; rw [sq, Finset.sum_mul_sum] rw [L, L, R, R, Finset.sum_div, Finset.sum_div, ← Finset.sum_sub_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun u _ => ?_ rw [Finset.sum_div, Finset.sum_div, ← Finset.sum_sub_distrib, ← Finset.sum_add_distrib] refine Finset.sum_congr rfl fun v _ => ?_ rw [hentry]; simp only [hy]; ring rw [e, hx, ← hyy] nlinarith [sq_nonneg (∑ v, y v)]