A Log-Free Lower Bound for the Number of Facets of $0/1$-Polytopes

Abstract

Let $g(n)$ denote the largest number of facets of a full-dimensional $0/1$-polytope in ${\mathbb{R}}^n$. We prove that there are absolute constants $c>0$ and $n_0$ such that $$g(n)\ge (cn{)}^{n/2}(n\ge n_0).$$ This removes the logarithmic factor from the lower bound $(cn/\log n{)}^{n/2}$ of Gatzouras, Giannopoulos, and Markoulakis. The proof compares a random sign polytope with two Rademacher rate bodies separated by a fixed level gap. Facets missing the inner body have uniformly small footprints on a flat patch of the outer body. A facet entering the inner body forces an empty buffered discrete cap. For shallow penetration, a likelihood-slab localization reduces the relevant range entropy and permits a conditional $\epsilon$-net argument; for deep penetration, a global discretization suffices.