Lemma 11 — , , has a face that is an extension of
ProvedExtensionComplexity.TSP.tsp_face_extends_corcorrelation-polytopep2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1reductiontsp-polytope
Lemma 11: for each there exists a positive integer such that contains a face that is an extension of . Precisely, there is a constant such that for every there are an integer with , a face of and a linear map with .
With Lemma 9 and Theorem 7 this gives with , which is the main theorem.
Formalization Note is a constant independent of with . The hypothesis is added: at no positive exists. The explicit value of in the paper's proof is not part of the statement.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_Polytope import Definitions.Def_ExtensionComplexity_TSP_CutCor import Definitions.Def_ExtensionComplexity_TSP_TSPPolytope
Formal statement
namespace ExtensionComplexity.TSP
/-- **Lemma 11** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:14): for each `n` there is a
positive integer `q = O(n²)` such that `TSP(q)` contains a face that is an extension of `COR(n)`.
`O(n²)` is a constant `c` with `q ≤ c·n²`, uniform in `n`; `n ≥ 1` is added because a positive
`q ≤ c·0²` cannot exist. -/
theorem tsp_face_extends_cor :
∃ c : ℕ, ∀ n : ℕ, 1 ≤ n → ∃ q : ℕ, 0 < q ∧ q ≤ c * n ^ 2 ∧
∃ F : Set (Edge q → ℝ), IsFace (tspPolytope q) F ∧ IsExtension F (corPolytope n) := 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:14, Lemma 11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.