Lemma 9 (i) — if is an extension of then
ProvedExtensionComplexity.TSP.xc_extension_monoextensionextension-complexitymonotonicityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be polytopes. Lemma 9 (i): if is an extension of , i.e. for some linear map , then
Extension complexity can only drop under linear projection; this is how a lower bound for becomes a lower bound for any polytope one of whose faces projects onto it.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ExtensionComplexity_TSP_Polytope
Formal statement
namespace ExtensionComplexity.TSP
/-- **Lemma 9 (i)** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:13): let `P` and `F` be
polytopes. If `F` is an extension of `P`, then `xc(F) ≥ xc(P)`. -/
theorem xc_extension_mono {ι κ : Type*} [Fintype ι] [Fintype κ] (P : Set (ι → ℝ))
(F : Set (κ → ℝ)) (hP : IsPolytope P) (hF : IsPolytope F) (hext : IsExtension F P) :
extensionComplexity P ≤ extensionComplexity F := 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 (i)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.