On Unavoidable Faces of High-Dimensional Polytopes

Abstract

Kalai's cube--simplex conjecture asserts that for all positive integers $\ell ,k$, there is an integer $f(\ell ,k)$ such that every polytope of dimension at least $f(\ell ,k)$ has either a simplex $\ell$-face or a cube $k$-face; let $f_s(\ell ,k)$ denote the threshold restricted to simple polytopes. Finiteness of $f(\ell ,k)$ is known only for $\ell ,k\le 2$. In addition, Kalai proved that $f_s(2,k)\le 2k^2$. Here we prove that $f_s(\ell ,k)$ is finite for all $\ell \ge 2$ and $k\ge 3$, the first such result beyond $\ell =2$, with $f_s(2,k)\le 2k^2-1$ and $f_s(\ell ,k)\le \frac{1}{2}{k}^2\ell 2^k$ for $\ell \ge 3$. In the opposite direction, we obtain the lower bounds $f(\ell ,k)\ge (5\lfloor \ell /2\rfloor +(\ell \mathrm{mod}2)-1)(k-1)+1$ and $f_s(\ell ,k)\ge \max \{4,2(\ell -1)\}(k-1)+1$. A companion question asks for the minimum possible size of a 3-face within a higher-dimensional polytope. Meisinger, Kleinschmidt and Kalai proved that every rational $d$-polytope with $d\ge 9$ has a $3$-face with fewer than $78$ vertices or fewer than $78$ facets. Here we improve their bound: every convex polytope of dimension at least $15$ has a $3$-face with at most $13$ facets. One step of our proof requires an explicit exact rational certificate or identity on flag numbers. This certificate is computed using linear programming.

27 pages, including 5 pages of appendix