Theorem 10 — graphs on vertices with
ProvedExtensionComplexity.TSP.xc_stab_lower_boundextension-complexitylower-boundp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1stable-set-polytope
Theorem 10: for all one can construct a graph with vertices such that the extension complexity of the stable set polytope is . That is, there are and such that for every there is a graph on vertices with
The worst-case extension complexity of stable set polytopes is therefore superpolynomial, in contrast with perfect graphs, whose stable set polytopes have compact semidefinite descriptions.
Formalization Note "One can construct" is stated as existence of the graph. is read as , with a real power. The stable set polytope is the published definition ChvatalPolytopes.Shared.stablePolytope.
Preamble
import Mathlib import Definitions.Def_ExtensionComplexity_TSP_extensionComplexity import Definitions.Def_ChvatalPolytopes_Shared_StablePolytope
Formal statement
namespace ExtensionComplexity.TSP
/-- **Theorem 10** (Fiorini et al., J. ACM 62(2) (2015), Art. 17, p. 17:14): for all `n` there is a
graph `G_n` with `n` vertices whose stable set polytope has extension complexity `2^{Ω(√n)}`:
there are `C > 0` and `N` such that every `n ≥ N` admits a graph `G` on `n` vertices with
`xc(STAB(G)) ≥ 2^{C√n}`. "One can construct" is stated as existence. -/
theorem xc_stab_lower_bound :
∃ C : ℝ, 0 < C ∧ ∃ N : ℕ, ∀ n ≥ N, ∃ G : SimpleGraph (Fin n),
(2 : ℝ) ^ (C * Real.sqrt n) ≤
(extensionComplexity (ChvatalPolytopes.Shared.stablePolytope G) : ℝ) := 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, Theorem 10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.