Lemma 6.11 — T_l = M_l^{1/2}; T_l = 1 iff l = ω, T_l > 1 iff l < ω, T_l < 1 iff l > ω
ProvedTensorNP.SpectralNorm.lemma_6_11clique-numberp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-normtensor
Let be a simple graph on vertices with clique number and edges enumerated as , , and let be a positive integer. Let
with and . Then
and therefore iff , iff , and iff .
This identifies the maximum of the multilinear form (26), the form of the tensor , with the square root of the Motzkin–Straus quantity , so that its comparison with detects the clique number.
Formalization Note and are the sSup-based definitions Tval and Mval; the statement holds for every edge enumeration. The paper's statement of Lemma 6.11 prints in the third sum; there is no in this section and the proof (p. 0:24) uses , which is formalized here (0-based: coordinates of ).
Preamble
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
namespace TensorNP.SpectralNorm
/-- **Lemma 6.11.** For a simple graph `G` on `v ≥ 1` vertices with clique number `ω`, any
enumeration `ε` of its `e` edges and any positive integer `l`, the maximum `T_l` of the form (26)
over `‖u‖₂ = ‖v‖₂ = ‖w‖₂ = 1` equals `M_l^{1/2}`; thus `T_l = 1` iff `l = ω`, `T_l > 1` iff
`l < ω`, and `T_l < 1` iff `l > ω`. -/
theorem lemma_6_11 {v e : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v)) [DecidableRel G.Adj]
(ε : Fin e ≃ G.edgeSet) (l : ℕ) (hl : 1 ≤ l) :
Tval G ε l = Real.sqrt (Mval G l) ∧
(Tval G ε l = 1 ↔ l = G.cliqueNum) ∧
(1 < Tval G ε l ↔ l < G.cliqueNum) ∧
(Tval G ε l < 1 ↔ G.cliqueNum < 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), pp. 0:23–0:24, Lemma 6.11, (26), and its proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.