Small extended formulations for cyclic polytopes (Q2351019): Difference between revisions

The extension complexity of a convex polytope P is the minimal number of linear inequalities describing a polytope that projects to P, i.e. the minimal number of facets of such a polytope. In general, the extension complexity of P may be much less that the number of facets of P itself. See [\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)] for a linear-algebraic reformulation of this notion. The main result of the present paper is as follows: the extension complexity of the d-dimensional cyclic polytope with \(n\) vertices does not exceed \(O(\log n)^{\lfloor d/2 \rfloor}\). For cyclic polygons, the proof is based on an explicit construction of a covering polytope with few facets. For arbitrary dimension, the proof is less straightforward and is based on the aforementioned algebraic reformulation of the extension complexity.