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 Rn. We prove that there are absolute constants c>0 and n0 such that g(n)≥ (cn)n/2 (n≥ n0). 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 ε-net argument; for deep penetration, a global discretization suffices.
Related
- Ehrhart positivity of smooth polytopes with few facets
- Equifacetted polytopes whose facets are products of simplices: The simplicial prism case
- An improved lower bound for the packing number of the 2-token graph of the cycle
- Compact Hyperbolic Coxeter Six-dimensional Polytopes With Ten Facets
- A new lower bound for the sixth Schur number: S(6)≥ 537
BibTeX
@misc{friedland2026logfree,
title = {{A Log-Free Lower Bound for the Number of Facets of $0/1$-Polytopes}},
author = {Omer Friedland},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.17127},
eprint = {2608.17127},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.17127},
}
RIS
TY - UNPB
TI - A Log-Free Lower Bound for the Number of Facets of 0/1-Polytopes
AU - Omer Friedland
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.17127
UR - https://arxiv.org/abs/2608.17127
AB - 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)≥ (cn)^n/2 (n≥ 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 ε-net argument; for deep penetration, a global discretization suffices.
ER -