Theorem 6.7 (Motzkin–Straus) — 1 − 1/ω(G) = 2 max over the simplex of Σ_{ij∈E} x_i x_j
ProvedTensorNP.SpectralNorm.theorem_6_7Let be a simple graph on vertices with clique number (the number of vertices of a largest clique), and let be the standard simplex. Then
where the sum runs over the unordered edges of , and the maximum is attained.
This classical theorem of Motzkin and Straus (1965) links the combinatorial quantity to a quadratic optimization problem over the simplex; it is the source of the value of in display (22).
Formalization Note The vertex set is Fin v and the clique number is Mathlib's SimpleGraph.cliqueNum. The statement is IsGreatest of the image of (Mathlib's stdSimplex ℝ (Fin v)) under , which asserts both that the value is attained and that it is an upper bound. The hypothesis (so ) excludes the empty graph, for which is not defined.
import Mathlib
namespace TensorNP.SpectralNorm
/-- **Theorem 6.7 (Motzkin–Straus).** Let `G` be a simple graph on `v ≥ 1` vertices with clique
number `ω(G)`. Over the standard simplex `Δ_v`, the maximum of `2 Σ_{{i,j} ∈ E} x_i x_j` (sum over
the unordered edges) is `1 − 1/ω(G)`. -/
theorem theorem_6_7 {v : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v)) [DecidableRel G.Adj] :
IsGreatest
((fun x : Fin v → ℝ =>
2 * ∑ s ∈ G.edgeFinset, Sym2.lift ⟨fun i j => x i * x j, fun i j => mul_comm _ _⟩ s) ''
stdSimplex ℝ (Fin v))
(1 - 1 / (G.cliqueNum : ℝ)) := by sorry
end TensorNP.SpectralNorm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.