标题： 多面体的扩展复杂性具有少量顶点或面 显示英文标题

标题： Extension complexity of polytopes with few vertices or facets

摘要： 我们研究顶点或面数量较少的多面体的扩展复杂性。一方面，我们根据其扩展复杂性对最多有$d+4$个顶点的$d$-多面体进行了完整的分类：在具有$d+4$个顶点的超指数多个$d$-多面体中，除了大小为$\theta(d^2)$的一些族外，其余所有多面体的扩展复杂性均为$d+4$。 另一方面，我们证明了具有$d+1+\alpha$个顶点/面的单纯/单纯$d$-多面体的通用实现的扩展复杂性至少为$2 \sqrt{d(d+\alpha)} -d + 1$，这表明对于所有$d>(\frac{\alpha-1}{2})^2$来说，存在具有$d+1+\alpha$个顶点或面的$d$-多面体，其扩展复杂性为$d+1+\alpha$。 显示英文摘要

摘要： 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$.