论文标题
低维层的扩展复杂性
Extension complexity of low-dimensional polytopes
论文作者
论文摘要
有时，可以将复杂的多层人士表示为更简单的多型的投影。为了量化这一现象，polytope $ p $的扩展复杂性被定义为（可能更高维）多层的最小相数，可以从中获得$ p $作为（线性）投影。该概念是由与组合优化相关性的动机，并且已经针对与重要优化问题相关的各种特定多面体进行了深入的研究。在本文中，我们将扩展复杂性研究为一般多型的参数，更具体地考虑了各种低维多形家族。 首先，我们证明，对于固定尺寸$ d $，随机$ d $尺寸的polytope的扩展复杂性（作为球或球体中随机点的凸壳获得）通常位于其顶点数量的平方根的顺序上。其次，我们证明任何环状$ n $ vertex polygon（其顶点位于圆上）具有扩展复杂性，最多$ 24 \ sqrt n $。这种界限紧密到恒定因子$ 24 $。最后，我们证明存在$ n^{o（1）} $ - 尺寸多层，最多$ n $ vertices和扩展复杂度$ n^{1-o（1）} $。我们的定理已通过一系列不同的技术证明，我们希望这会进一步引起人们的兴趣。
Sometimes, it is possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope $P$ is defined to be the minimum number of facets of a (possibly higher-dimensional) polytope from which $P$ can be obtained as a (linear) projection. This notion is motivated by its relevance to combinatorial optimisation, and has been studied intensively for various specific polytopes associated with important optimisation problems. In this paper we study extension complexity as a parameter of general polytopes, more specifically considering various families of low-dimensional polytopes. First, we prove that for a fixed dimension $d$, the extension complexity of a random $d$-dimensional polytope (obtained as the convex hull of random points in a ball or on a sphere) is typically on the order of the square root of its number of vertices. Second, we prove that any cyclic $n$-vertex polygon (whose vertices lie on a circle) has extension complexity at most $24\sqrt n$. This bound is tight up to the constant factor $24$. Finally, we show that there exists an $n^{o(1)}$-dimensional polytope with at most $n$ vertices and extension complexity $n^{1-o(1)}$. Our theorems are proved with a range of different techniques, which we hope will be of further interest.
