Lemma 9 (ii) — if is a face of then
ProvedExtensionComplexity.TSP.xc_face_monoextension-complexityfacemonotonicityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be polytopes. Lemma 9 (ii): if is a face of (either itself or the intersection of with a valid hyperplane), then
A face is never harder to describe than the whole polytope. Together with part (i) it reduces lower bounds for and to the lower bound for .
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_Polytope
Formal statement
namespace ExtensionComplexity.TSP
/-- **Lemma 9 (ii)** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:13): let `Q` and `F` be
polytopes. If `F` is a face of `Q`, then `xc(Q) ≥ xc(F)`. -/
theorem xc_face_mono {κ : Type*} [Fintype κ] (Q F : Set (κ → ℝ)) (hQ : IsPolytope Q)
(hF : IsPolytope F) (hface : IsFace Q F) :
extensionComplexity F ≤ extensionComplexity Q := 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:13, Lemma 9 (ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.