On Unavoidable Faces of High-Dimensional Polytopes
Abstract
Kalai's cube--simplex conjecture asserts that for all positive integers ℓ,k, there is an integer f(ℓ,k) such that every polytope of dimension at least f(ℓ,k) has either a simplex ℓ-face or a cube k-face; let fs(ℓ,k) denote the threshold restricted to simple polytopes. Finiteness of f(ℓ,k) is known only for ℓ,k ≤ 2. In addition, Kalai proved that fs(2,k) ≤ 2k2. Here we prove that fs(ℓ,k) is finite for all ℓ ≥ 2 and k ≥ 3, the first such result beyond ℓ = 2, with fs(2,k) ≤ 2k2−1 and fs(ℓ,k) ≤ 1/2k2ℓ 2k for ℓ ≥ 3. In the opposite direction, we obtain the lower bounds f(ℓ,k) ≥ (5⌊ ℓ/2 ⌋ + (ℓ bmod 2) − 1)(k−1)+1 and fs(ℓ,k) ≥ max{4, 2(ℓ−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 ≥ 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.
Related
- Berry--Esseen Bounds for Faces in Unimodular Triangulations of Random Polytopes
- Integer decomposition property of three-dimensional smooth polytopes: a shorter proof
- Compact Hyperbolic Coxeter Six-dimensional Polytopes With Ten Facets
- Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
- Unavoidable flats in matroids excluding a uniform minor
BibTeX
@misc{loera2026unavoidable,
title = {{On Unavoidable Faces of High-Dimensional Polytopes}},
author = {Jesús A. De Loera and Ethan X. Fang and Shengtao Guo and Junwei Lu and Hailun Zheng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00397},
eprint = {2609.00397},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00397},
}
RIS
TY - UNPB
TI - On Unavoidable Faces of High-Dimensional Polytopes
AU - Jesús A. De Loera
AU - Ethan X. Fang
AU - Shengtao Guo
AU - Junwei Lu
AU - Hailun Zheng
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00397
UR - https://arxiv.org/abs/2609.00397
AB - Kalai's cube--simplex conjecture asserts that for all positive integers ℓ,k, there is an integer f(ℓ,k) such that every polytope of dimension at least f(ℓ,k) has either a simplex ℓ-face or a cube k-face; let f_s(ℓ,k) denote the threshold restricted to simple polytopes. Finiteness of f(ℓ,k) is known only for ℓ,k ≤ 2. In addition, Kalai proved that f_s(2,k) ≤ 2k^2. Here we prove that f_s(ℓ,k) is finite for all ℓ ≥ 2 and k ≥ 3, the first such result beyond ℓ = 2, with f_s(2,k) ≤ 2k^2−1 and f_s(ℓ,k) ≤ 1/2k^2ℓ 2^k for ℓ ≥ 3. In the opposite direction, we obtain the lower bounds f(ℓ,k) ≥ (5⌊ ℓ/2 ⌋ + (ℓ bmod 2) − 1)(k−1)+1 and f_s(ℓ,k) ≥ max{4, 2(ℓ−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 ≥ 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.
ER -