A Log-Free Lower Bound for the Number of Facets of $0/1$-Polytopes
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.17127
curl -X POST /api/v1/records/arxiv/2608.17127/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.17127/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'