Extension complexity of polytopes with few vertices or facets

Abstract

We study the extension complexity of polytopes with few vertices or facets. On the one hand, we provide a complete classification of $d$-polytopes with at most $d+4$ vertices according to their extension complexity: Out of the super-exponentially many $d$-polytopes with $d+4$ vertices, all have extension complexity $d+4$ except for some families of size $\theta (d^2)$. On the other hand, we show that generic realizations of simplicial/simple $d$-polytopes with $d+1+\alpha$ vertices/facets have extension complexity at least $2\sqrt{d(d+\alpha )}-d+1$, which shows that for all $d>(\frac{\alpha -1}{2}{)}^2$ there are $d$-polytopes with $d+1+\alpha$ vertices or facets and extension complexity $d+1+\alpha$.

arXiv comment17 pages, 3 figures. v2: minor corrections, improved exposition