b5_clique_bound_iff
For B_5(n_0..n_4) with all n_i ≥ 1, the strong spectral clique bound sqrt(Σ_{λ ≠ -1} λ^2) ≤ n(1 - 1/ω) (with Σ_{λ≠-1} λ^2 = tr(M^2) for the quotient matrix M) holds if and only if (n_0, n_1, n_2, n_3) is not (1,1,1,1), (1,1,1,2) or (1,2,1,1) (in the paper's vertex order r_1, r_2, w_1, w_2, r_3); so it fails exactly on three infinite one-parameter families B_5(1,1,1,1,c), B_5(1,1,1,2,c), B_5(1,2,1,1,c).
Statement
theorem b5_clique_bound_iff (n : Fin 5 → ℕ) (hpos : ∀ i, 1 ≤ n i) :
Real.sqrt ((b5_quotient_matrix n ^ 2).trace)
≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b5_graph n).cliqueNum : ℝ)) ↔
¬ (n 0 = 1 ∧ n 2 = 1 ∧ ((n 1 = 1 ∧ n 3 = 1) ∨ (n 1 = 1 ∧ n 3 = 2) ∨ (n 1 = 2 ∧ n 3 = 1)))- Related work
- arXiv:2610.21388 (Stronger spectral bound for clique number): Theorems 3.1 and 3.5 prove the bound for B_3 and B_4 with one exceptional family / one exceptional graph; the example after Theorem 3.5 shows it fails for B_5(1,2,1,1,1) and says that for t = 5 'there may be additional parameter choices for which our bound fails'. This characterizes them
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- b5_graphThe graph B_5(n_1..n_5) of arXiv:2610.21388: each vertex i of G_5 is replaced by a clique of n_i vertices, and cliques of adjacent…
- b5_quotient_matrixM_ii = n_i - 1, M_ij = a_ij n_j (a = adjacency of G_5); the eigenvalues of M are those of B_5 other than -1 (Theorem 2.3 of…
- b5_quotient_trace_sqtr(M^2) = Σ (n_i - 1)^2 + 2 (n_0 n_1 + n_2 n_3 + n_1 n_3 + n_4 (n_0 + n_1 + n_2 + n_3)) for the quotient matrix of B_5.
- b5_cliqueNumω(B_5(n_0..n_4)) = n_4 + max(n_0 + n_1, n_1 + n_3, n_2 + n_3).
- b5_gap_nonnegFor positive integers a, b, c, d, e with (a,b,c,d) ∉ {(1,1,1,1), (1,1,1,2), (1,2,1,1)}: tr ≤ n^2 (1 - 1/ω)^2 where tr = Σ (x-1)^2 + 2(ab +…
- b5_clique_bound_fails_of_exceptionalFor (n_0, n_1, n_2, n_3) ∈ {(1,1,1,1), (1,1,1,2), (1,2,1,1)} and every n_4 = e ≥ 1, n^2 (1 - 1/ω)^2 < tr(M^2), i.e. the strong bound fails…
The proof, explained
The proof expresses the strong spectral clique bound √(tr(M^2)) ≤ N(1 - 1/ω) as an explicit inequality in the block sizes n_0, ..., n_4. Because the clique number ω ≥ 1 and the block sizes are positive, the right-hand side is non-negative, allowing the square root to be removed by squaring both sides. The equivalence is then completed by two known results: the bound strictly fails on the three exceptional parameter families by b5_clique_bound_fails_of_exceptional, and holds non-negatively on all other positive tuples by b5_gap_nonneg.
The spectral clique bound is expressed directly in terms of the block sizes n_0, ..., n_4.
The trace of the squared quotient matrix is rewritten using b5_quotient_trace_sq and the graph clique number ω is rewritten using b5_cliqueNum. The finite sums over Fin 5 on both sides are then expanded into explicit sums of the five block sizes using Fin.sum_univ_five.
uses
b5_quotient_trace_sq,b5_cliqueNum,Fin.sum_univ_fiverw [b5_quotient_trace_sq, b5_cliqueNum] simp only [Fin.sum_univ_five]
The bound √(tr(M^2)) ≤ N(1 - 1/ω) is equivalent to the squared inequality tr(M^2) ≤ (N(1 - 1/ω))^2.
Because n_4 ≥ 1, the clique number ω = n_4 + max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3) is at least 1, so ω > 0. This implies 1/ω ≤ 1, whence 1 - 1/ω ≥ 0. Since each n_i ≥ 1, the total vertex count N = ∑ n_i is non-negative, and therefore the right-hand side Y = N(1 - 1/ω) is non-negative by mul_nonneg. By Real.sqrt_le_left, √(tr(M^2)) ≤ Y is equivalent to tr(M^2) ≤ Y^2.
uses
le_trans,Nat.le_add_right,lt_of_lt_of_le,zero_lt_one,div_le_one,mul_nonneg,Real.sqrt_le_lefthave hW1 : (1:ℝ) ≤ ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by have h := hpos 4 have h2 : (1:ℕ) ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := le_trans h (Nat.le_add_right _ _) exact_mod_cast h2 have hWpos : (0:ℝ) < ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := lt_of_lt_of_le zero_lt_one hW1 have hfrac : (0:ℝ) ≤ 1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by have h3 : (1:ℝ) / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) ≤ 1 := by rw [div_le_one hWpos]; exact hW1 linarith have hNnn : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) := by positivity have hY : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) * (1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ)) := mul_nonneg hNnn hfrac rw [Real.sqrt_le_left hY]
For all real numbers A and B, (A * B)^2 = A^2 * B^2.
This algebraic identity distributing the square over multiplication is established by ring arithmetic.
have hsq : ∀ A B : ℝ, (A * B) ^ 2 = A ^ 2 * B ^ 2 := fun A B => by ring
If the spectral clique bound holds, then (n_0, n_1, n_2, n_3) is not any of the three exceptional tuples (1,1,1,1), (1,1,1,2), or (1,2,1,1).
Assume the bound holds and suppose for contradiction that the tuple is exceptional. By b5_clique_bound_fails_of_exceptional, the strict inequality (N(1 - 1/ω))^2 < tr(M^2) holds for all such tuples. Rewriting the squared product (N(1 - 1/ω))^2 as N^2(1 - 1/ω)^2 produces an immediate contradiction with the assumed bound tr(M^2) ≤ N^2(1 - 1/ω)^2.
uses
b5_clique_bound_fails_of_exceptionalconstructor · intro hle hexc have hgt := b5_clique_bound_fails_of_exceptional (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 4) hexc rw [hsq] at hle linarith
If (n_0, n_1, n_2, n_3) is not exceptional, then the spectral clique bound holds.
Assuming the tuple is not exceptional, b5_gap_nonneg provides tr(M^2) ≤ N^2(1 - 1/ω)^2. Rewriting this via the identity (A*B)^2 = A^2*B^2 yields the desired squared bound tr(M^2) ≤ (N(1 - 1/ω))^2.
uses
b5_gap_nonneg· intro hne have hge := b5_gap_nonneg (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 0) (hpos 1) (hpos 2) (hpos 3) (hpos 4) hne rwa [hsq]
b5_quotient_trace_sq- The trace of the squared quotient matrix of B_5(n) is ∑_{i=0}^4 (n_i - 1)^2 + 2(n_0 n_1 + n_2 n_3 + n_1 n_3 + n_4(n_0 + n_1 + n_2 + n_3)).
b5_cliqueNum- The clique number of B_5(n) equals n_4 + max(max(n_0 + n_1, n_1 + n_3), n_2 + n_3).
Fin.sum_univ_five- The sum of a 5-element sequence over Fin 5 is the sum of its values at indices 0, 1, 2, 3, and 4.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Nat.le_add_right- For any natural numbers n and k, n ≤ n + k.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
zero_lt_one- In an ordered semiring, 0 < 1.
div_le_one- For b > 0, the quotient a / b ≤ 1 if and only if a ≤ b.
mul_nonneg- The product of two non-negative numbers is non-negative.
Real.sqrt_le_left- For y ≥ 0, √x ≤ y if and only if x ≤ y^2.
b5_clique_bound_fails_of_exceptional- For the exceptional parameter choices where (n_0, n_2) = (1, 1) and (n_1, n_3) ∈ {(1, 1), (1, 2), (2, 1)}, the squared spectral clique bound strictly fails: (N(1 - 1/ω))^2 < tr(M^2).
b5_gap_nonneg- For any non-exceptional tuple of positive block sizes, the squared spectral clique bound holds: tr(M^2) ≤ N^2 (1 - 1/ω)^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.
theorem b5_clique_bound_iff (n : Fin 5 → ℕ) (hpos : ∀ i, 1 ≤ n i) : Real.sqrt ((b5_quotient_matrix n ^ 2).trace) ≤ (∑ i, (n i : ℝ)) * (1 - 1 / ((b5_graph n).cliqueNum : ℝ)) ↔ ¬ (n 0 = 1 ∧ n 2 = 1 ∧ ((n 1 = 1 ∧ n 3 = 1) ∨ (n 1 = 1 ∧ n 3 = 2) ∨ (n 1 = 2 ∧ n 3 = 1))) := by rw [b5_quotient_trace_sq, b5_cliqueNum] simp only [Fin.sum_univ_five] have hW1 : (1:ℝ) ≤ ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by have h := hpos 4 have h2 : (1:ℕ) ≤ n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) := le_trans h (Nat.le_add_right _ _) exact_mod_cast h2 have hWpos : (0:ℝ) < ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := lt_of_lt_of_le zero_lt_one hW1 have hfrac : (0:ℝ) ≤ 1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) := by have h3 : (1:ℝ) / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ) ≤ 1 := by rw [div_le_one hWpos]; exact hW1 linarith have hNnn : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) := by positivity have hY : (0:ℝ) ≤ (↑(n 0) + ↑(n 1) + ↑(n 2) + ↑(n 3) + ↑(n 4)) * (1 - 1 / ((n 4 + max (max (n 0 + n 1) (n 1 + n 3)) (n 2 + n 3) : ℕ) : ℝ)) := mul_nonneg hNnn hfrac rw [Real.sqrt_le_left hY] have hsq : ∀ A B : ℝ, (A * B) ^ 2 = A ^ 2 * B ^ 2 := fun A B => by ring constructor · intro hle hexc have hgt := b5_clique_bound_fails_of_exceptional (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 4) hexc rw [hsq] at hle linarith · intro hne have hge := b5_gap_nonneg (n 0) (n 1) (n 2) (n 3) (n 4) (hpos 0) (hpos 1) (hpos 2) (hpos 3) (hpos 4) hne rwa [hsq]