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 $\R^n$. We prove that there are absolute constants $c>0$ and $n_0$ such that $$ g(n)\ge (cn)^{n/2}\quad(n\ge n_0). $$ This removes the logarithmic factor from the lower bound $\bigl(cn/\log n\bigr)^{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 $\varepsilon$-net argument; for deep penetration, a global discretization suffices.

Disclosure

“d in Section 5; and the buffered-cap estimate is proved in Section 6. The two sampling estimates are included in Appendix A. Disclosure of AI assistance. During the development of the final argument, the author used Chat- GPT, developed by OpenAI, extensively for mathematical exploration, including proposing, testing, and refining proof strategies, and for assistance with the organization and exposition of the proof. The project, together with several partial approaches and interme”

PDF page 2

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:20:47.932558Z

Structural counts