Lemma 8 — , , has a face that is an extension of
ProvedExtensionComplexity.TSP.stab_face_extends_corFor a graph the stable set polytope is the convex hull of the characteristic vectors of the stable sets of . Lemma 8: for each there exists a graph with vertices such that contains a face that is an extension of . Precisely, there is a constant such that for every there are , a graph on vertices and a face of with a linear map satisfying .
With Lemma 9 this transfers the lower bound of Theorem 7 to stable set polytopes (Theorem 10).
Formalization Note The stable set polytope is the published definition ChvatalPolytopes.Shared.stablePolytope (convex hull of incidence vectors of independent sets, in ). is a constant independent of with . The statement is for all including , where it holds with the empty graph.
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_Polytope import Definitions.Def_ExtensionComplexity_TSP_CutCor import Definitions.Def_ChvatalPolytopes_Shared_StablePolytope
namespace ExtensionComplexity.TSP
/-- **Lemma 8** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:12): for each `n` there is a
graph `H_n` with `O(n²)` vertices such that `STAB(H_n)` contains a face that is an extension of
`COR(n)`. `O(n²)` is a constant `c` with at most `c·n²` vertices, uniform in `n`. -/
theorem stab_face_extends_cor :
∃ c : ℕ, ∀ n : ℕ, ∃ m : ℕ, m ≤ c * n ^ 2 ∧ ∃ H : SimpleGraph (Fin m),
∃ F : Set (Fin m → ℝ), IsFace (ChvatalPolytopes.Shared.stablePolytope H) F ∧
IsExtension F (corPolytope n) := by sorry
end ExtensionComplexity.TSP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.