Extension Complexity of Independent Set Polytopes

Mika Göös, Rahul Jain, Thomas Watson

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega (n/\log n)$. Previously, no explicit examples of $n$-dimensional…