Lemma 6 — is valid for with slack at
ProvedExtensionComplexity.TSP.cor_valid_inequality_slackcorrelation-polytopep2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1slack-matrixvalid-inequality
For consider the inequality
where is the Frobenius inner product and the diagonal matrix with on its diagonal. Lemma 6: for every ,
- inequality (5) is valid for , i.e. holds for every ;
- the slack of the vertex with respect to (5) is precisely :
Hence the submatrix of a slack matrix of formed by the inequalities (5) and the vertices is exactly .
Formalization Note is a vector indexed by ordered pairs , and the Frobenius product is the dot product over all ordered pairs.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_CorrelationMatrix import Definitions.Def_ExtensionComplexity_TSP_CutCor
Formal statement
namespace ExtensionComplexity.TSP
/-- **Lemma 6** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:12): for all `a ∈ {0,1}^n`,
the inequality `⟨2 diag(a) − aaᵀ, x⟩ ≤ 1` (5) is valid for `COR(n)`, and the slack of the vertex
`x = bbᵀ` with respect to (5) is precisely `M_ab`. `⟨·,·⟩` is the Frobenius inner product, the
sum over ordered pairs `(i, j)`. -/
theorem cor_valid_inequality_slack {n : ℕ} (a : Fin n → Bool) :
(∀ x ∈ corPolytope n, corIneqCoeff a ⬝ᵥ x ≤ 1) ∧
∀ b : Fin n → Bool, 1 - corIneqCoeff a ⬝ᵥ outerBits b = matM n a b := by sorry
end ExtensionComplexity.TSP
Source
Fiorini, Massar, Pokutta, Tiwary, de Wolf, Exponential lower bounds for polytopes in combinatorial optimization, J. ACM 62(2) (2015), Art. 17, p. 17:12, Lemma 6 and inequality (5); p. 17:8, eq. (4) and footnote 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.