Centrally Symmetric Polytopes with Many Faces.

Abstract

We study the convex hull of the symmetric moment curve $U_k(t)=(cos t, sin t, cos 3t, sin 3t, ldots, cos (2k-1)t, sin (2k-1)t)$ in ${mathbb R}^{2k}$ and provide deterministic constructions of centrally symmetric polytopes with a record high number faces. In particular, we prove that as long as $k$ distinct points $t_1, ldots, t_k$ lie in an arc of a certain length $phi_k > pi/2$, the points $U_k(t_1), ldots, U_k(t_k)$ span a face of the convex hull of $U_k(t)$. Based on this, we obtain deterministic constructions of $d$-dimensional centrally symmetric 2-neighborly polytopes with approximately $3^{d/2}$ vertices. More generally, for a fixed $k$, we obtain deterministic constructions of $d$-dimensional centrally symmetric $k$-neighborly polytopes with exponentially many in $d$ vertices, and of $d$-dimensional centrally symmetric polytopes with an arbitrarily large number of vertices and the density of $k$-faces approaching 1 exponentially fast with the dimension.