b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one
If n_0 = n_1 = 1 and n_2 ≥ 1, then for G = B_3(1, 1, n_2) the bound fails strictly: n(1 - 1/ω(G)) < sqrt(λ_1^2 + λ_2^2 + λ_3^2) (with the sum of squares as tr(M^2)).
Statement
theorem b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one (n : Fin 3 → ℕ) (h2 : 1 ≤ n 2)
(h0 : n 0 = 1) (h1 : n 1 = 1) :
(∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ))
< Real.sqrt ((b3_quotient_matrix n ^ 2).trace)- Formalizes
- arXiv:2610.21388 (Stronger spectral bound for clique number), Theorem 3.1 ("in particular" part: D(1,1,n_3) < 0). Sum of squares of eigenvalues other than -1 stated as tr(M^2) of the quotient matrix
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- b3_graphThe graph B_3(n_0, n_1, n_2) on the disjoint union of blocks of sizes n_0, n_1, n_2: two distinct vertices are adjacent iff they lie in…
- b3_quotient_matrixThe 3x3 quotient matrix M = [[n_0 - 1, 0, n_2], [0, n_1 - 1, n_2], [n_0, n_1, n_2 - 1]] of B_3(n_0, n_1, n_2), whose three eigenvalues are…
- b3_quotient_trace_sqtr(M^2) = n_0^2 + n_1^2 - n_2^2 + 2 n n_2 + 3 - 2n for the quotient matrix M of B_3(n_0,n_1,n_2), n = n_0 + n_1 + n_2; this is the sum of…
- b3_cliqueNumThe clique number of B_3(n_0, n_1, n_2) is max(n_0 + n_2, n_1 + n_2).
The proof, explained
The proof shows that the Motzkin–Straus-type clique bound fails strictly for the graph family $B_3(1, 1, n_2)$ with $n_2 \ge 1$ by explicitly calculating both sides. Under $n_0 = n_1 = 1$, the total vertex count is $n_2 + 2$, the clique number is $n_2 + 1$, and the trace of the squared quotient matrix is $(n_2 + 1)^2$, with square root $n_2 + 1$. The bound then simplifies to $\frac{n_2(n_2 + 2)}{n_2 + 1} < n_2 + 1$, which reduces upon clearing denominators to $n_2^2 + 2n_2 < n_2^2 + 2n_2 + 1$, a strict inequality.
The sum of vertex counts $\sum_{i} n_i$ equals $n_2 + 2$.
Expanding the three-element sum using `Fin.sum_univ_three` and substituting the hypotheses $n_0 = 1$ and $n_1 = 1$, the sum simplifies to $1 + 1 + n_2 = n_2 + 2$.
uses
Fin.sum_univ_threehave hsum : (∑ i, (n i : ℝ)) = (n 2 : ℝ) + 2 := by rw [Fin.sum_univ_three, h0, h1]; push_cast; ring
The clique number $\omega(G)$ of the graph is $n_2 + 1$.
By `b3_cliqueNum`, the clique number is $\max(n_0 + n_2, n_1 + n_2)$. Since $n_0 = n_1 = 1$, this becomes $\max(1 + n_2, 1 + n_2) = n_2 + 1$.
uses
b3_cliqueNumhave hclique : ((b3_graph n).cliqueNum : ℝ) = (n 2 : ℝ) + 1 := by rw [b3_cliqueNum, h0, h1] have hmax : max (1 + n 2) (1 + n 2) = n 2 + 1 := by omega rw [hmax]; push_cast; ring
The trace of the squared quotient matrix is $(n_2 + 1)^2$.
Using `b3_quotient_trace_sq` and substituting $n_0 = 1$ and $n_1 = 1$, algebraic simplification yields $1 + 1 - n_2^2 + 2(2 + n_2)n_2 + 3 - 2(2 + n_2) = (n_2 + 1)^2$.
uses
b3_quotient_trace_sqhave htrace : (b3_quotient_matrix n ^ 2).trace = ((n 2 : ℝ) + 1) ^ 2 := by rw [b3_quotient_trace_sq, h0, h1]; push_cast; ring
The main inequality simplifies to $(n_2 + 2)(1 - \frac{1}{n_2 + 1}) < n_2 + 1$.
Substituting the simplified vertex sum, clique number, and trace into the goal, the square root $\sqrt{(n_2 + 1)^2}$ evaluates to $n_2 + 1$ by `Real.sqrt_sq`, since $n_2 + 1 \ge 0$.
uses
Real.sqrt_sqrw [hsum, hclique, htrace, Real.sqrt_sq (by positivity)]
The left-hand side $(n_2 + 2)(1 - \frac{1}{n_2 + 1})$ equals $\frac{n_2(n_2 + 2)}{n_2 + 1}$.
Writing $1 - \frac{1}{n_2 + 1}$ over a common denominator gives $\frac{n_2}{n_2 + 1}$, so multiplying by $n_2 + 2$ results in $\frac{n_2(n_2 + 2)}{n_2 + 1}$.
have hfun : ((n 2 : ℝ) + 2) * (1 - 1 / ((n 2 : ℝ) + 1)) = ((n 2 : ℝ) * ((n 2 : ℝ) + 2)) / ((n 2 : ℝ) + 1) := by field_simp; ring
The inequality holds strictly.
Replacing the left-hand side by $\frac{n_2(n_2 + 2)}{n_2 + 1}$ and clearing the positive denominator $n_2 + 1$ via `div_lt_iff₀`, the inequality reduces to $n_2(n_2 + 2) < (n_2 + 1)^2$. Expanding both sides gives $n_2^2 + 2n_2 < n_2^2 + 2n_2 + 1$, which holds strictly for all $n_2$. Non-linear arithmetic (`nlinarith`) closes the goal.
uses
div_lt_iff₀rw [hfun, div_lt_iff₀ (by positivity)] nlinarith
Fin.sum_univ_three- For any function $f$ on `Fin 3` into an additive commutative monoid, the sum over all three elements equals $f(0) + f(1) + f(2)$.
b3_cliqueNum- The clique number of the graph $B_3(n)$ is $\max(n_0 + n_2, n_1 + n_2)$.
b3_quotient_trace_sq- The trace of the squared quotient matrix of $B_3(n)$ equals $n_0^2 + n_1^2 - n_2^2 + 2(n_0 + n_1 + n_2)n_2 + 3 - 2(n_0 + n_1 + n_2)$.
Real.sqrt_sq- For any real number $x \ge 0$, the square root of $x^2$ is $x$.
div_lt_iff₀- For positive $c > 0$ in a ordered group with zero, $b / c < a \iff b < a \cdot c$.
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 b3_sqrt_trace_quotient_sq_gt_clique_bound_of_one_one (n : Fin 3 → ℕ) (h2 : 1 ≤ n 2) (h0 : n 0 = 1) (h1 : n 1 = 1) : (∑ i, (n i : ℝ)) * (1 - 1 / ((b3_graph n).cliqueNum : ℝ)) < Real.sqrt ((b3_quotient_matrix n ^ 2).trace) := by have hsum : (∑ i, (n i : ℝ)) = (n 2 : ℝ) + 2 := by rw [Fin.sum_univ_three, h0, h1]; push_cast; ring have hclique : ((b3_graph n).cliqueNum : ℝ) = (n 2 : ℝ) + 1 := by rw [b3_cliqueNum, h0, h1] have hmax : max (1 + n 2) (1 + n 2) = n 2 + 1 := by omega rw [hmax]; push_cast; ring have htrace : (b3_quotient_matrix n ^ 2).trace = ((n 2 : ℝ) + 1) ^ 2 := by rw [b3_quotient_trace_sq, h0, h1]; push_cast; ring rw [hsum, hclique, htrace, Real.sqrt_sq (by positivity)] have hfun : ((n 2 : ℝ) + 2) * (1 - 1 / ((n 2 : ℝ) + 1)) = ((n 2 : ℝ) * ((n 2 : ℝ) + 2)) / ((n 2 : ℝ) + 1) := by field_simp; ring rw [hfun, div_lt_iff₀ (by positivity)] nlinarith