Treewidth-exponential extension complexity for correlation polytopes

Conjecture 2 · arXiv:1806.00541

arXiv Conjecture high confidence— first stated 2018-10-18

Authors: Pierre Aboulker, Samuel Fiorini, Tony Huynh, Marco Macchia, Johanna Seif

Status open high confidence

The source paper proves the matching upper bound 2^{O(tw(G)+log n)} for the extension complexity of COR(G) and establishes tightness for minor-closed graph classes, but Conjecture 2 — that 2^{Omega(tw(G)+log n)} holds for every n-vertex graph G — remains open in full generality. Five web searches spanning 2019–2026 found no follow-up paper proving or disproving the conjecture for arbitrary graphs. The conjecture would imply 2^{Omega(n)} extension complexity for the stable set polytope of dense graphs and explicit 0/1-polytopes with extension complexity exponential in their dimension.

Reviewer notes. No follow-up found resolving Conjecture 2 in full generality. The paper does prove tightness for graphs in minor-closed classes (e.g. planar graphs), but the conjecture asks for all n-vertex graphs. The related Springer paper 'New limits of treewidth-based tractability in optimization' (Math. Program. 2021) could not be accessed but appears to address parameterized complexity limits rather than the exact conjecture. arXiv:2106.11945 (Smaller Extended Formulations for Spanning Tree Polytopes) is unrelated.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every $n$-vertex graph $G$, the extension complexity of $\mathrm{COR}(G)$ is $2^{\Omega(\mathrm{tw}(G)+\log n)}$.

Context

The authors prove the matching upper bound $2^{O(\mathrm{tw}(G)+\log n)}$ in Theorem 1 and conjecture that this is tight in general. If true, the conjecture would improve the bound of Göös, Jain and Watson ($2^{\Omega(n/\log n)}$ for the stable set polytope) to $2^{\Omega(n)}$, and would yield explicit 0/1-polytopes with extension complexity exponential in their dimension, as predicted by the counting argument of Rothvoß.

Notes. The paper proves this conjecture for the special case of proper minor-closed graph classes (Theorem 3), but the general statement remains open.

Source paper

Extension Complexity of the Correlation Polytope
Pierre Aboulker, Samuel Fiorini, Tony Huynh, Marco Macchia, Johanna Seif · 2018-10-18
https://arxiv.org/abs/1806.00541 PDF source