Lemma 6.8 — M_l = N_l for every graph
ProvedTensorNP.SpectralNorm.lemma_6_8clique-numbergraph-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-optimization
Let be a simple graph on vertices with edges , , enumerated in any order, and let be a positive integer. With and
where , we have
The lemma rewrites the simplex program as an optimization over the unit sphere, in the form that the Cauchy–Schwarz step of Lemma 6.11 produces.
Formalization Note Both maxima are the sSup-based definitions Mval and Nval; the statement holds for every enumeration ε : Fin e ≃ G.edgeSet. The hypotheses and are the section's standing assumptions.
Preamble
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
namespace TensorNP.SpectralNorm
/-- **Lemma 6.8.** For every simple graph `G` on `v ≥ 1` vertices, every enumeration `ε` of its
edges and every positive integer `l`, `M_l = N_l`. -/
theorem lemma_6_8 {v e : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v)) [DecidableRel G.Adj]
(ε : Fin e ≃ G.edgeSet) (l : ℕ) (hl : 1 ≤ l) :
Mval G l = Nval G ε l := by sorry
end TensorNP.SpectralNorm
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:23, Lemma 6.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.