§6, display before (22) and (22) — M_l = 1 + (ω − l)/(lω); M_ω = 1, M_l > 1 for l < ω, M_l < 1 for l > ω
ProvedTensorNP.SpectralNorm.display_22clique-numbergraph-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1quadratic-optimization
Let be a simple graph on vertices with clique number , let be a positive integer, , and . Then the maximum is attained and
Consequently , and
This translates the Motzkin–Straus theorem into a family of quadratic programs, indexed by , whose optimal value crosses exactly at .
Formalization Note The first clause is IsGreatest of the image of the simplex under with value ; the second says that the sSup-based definition Mval G l has this value. Hypotheses and are the paper's standing ones ( is a "positive integer", and requires a nonempty vertex set).
Preamble
import Mathlib import Definitions.Def_TensorNP_SpectralNorm_Tensor import Definitions.Def_TensorNP_SpectralNorm_CliqueTensor
Formal statement
namespace TensorNP.SpectralNorm
open Matrix
/-- **The value of `M_l` and (22)** (p. 0:22). For a simple graph `G` on `v ≥ 1` vertices with
clique number `ω` and a positive integer `l`, the maximum of `xᵀ Q_l x` over `Δ_v` is
`1 + (ω − l)/(lω)`; hence `M_ω = 1`, `M_l > 1` if `l < ω`, and `M_l < 1` if `l > ω`. -/
theorem display_22 {v : ℕ} (hv : 0 < v) (G : SimpleGraph (Fin v)) [DecidableRel G.Adj]
(l : ℕ) (hl : 1 ≤ l) :
IsGreatest ((fun x : Fin v → ℝ => x ⬝ᵥ (Qmat G l *ᵥ x)) '' stdSimplex ℝ (Fin v))
(1 + ((G.cliqueNum : ℝ) - l) / ((l : ℝ) * G.cliqueNum)) ∧
Mval G l = 1 + ((G.cliqueNum : ℝ) - l) / ((l : ℝ) * G.cliqueNum) ∧
(l = G.cliqueNum → Mval G l = 1) ∧
(l < G.cliqueNum → 1 < Mval G l) ∧
(G.cliqueNum < l → Mval G l < 1) := 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:22, display defining M_l and (22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.