Many Facets in Random Polytopes from Product and Log-Concave Measures

Abstract

We prove bounds of order $n^{n/2}{e}^{O(n)}$ for the expected number of facets of high-dimensional random polytopes. First, let $\mu$ be a non-degenerate compactly supported even probability measure on $\mathbb{R}$ satisfying $\mu ([x^{\ast }-s,x^{\ast }])\asymp s^{\kappa }$ near its right endpoint $x^{\ast }$. For every sufficiently small fixed $\alpha >0$, the convex hull of $N=\lfloor e^{\alpha n}\rfloor$ independent points with law ${\mu }^{\otimes n}$ has at least $n^{n/2}{e}^{-C_{\mu ,\alpha }n}$ expected facets; this includes all symmetric finite-alphabet distributions. For every full-dimensional log-concave probability measure on ${\mathbb{R}}^n$, we prove that there exist $T\in [n,2n]$ and $N=\lceil e^T{n}^{3/2}\rceil$ for which \[ n^{n/2}e^{-Cn} \leq \mathbb E f_{n-1}(P_N) \leq n^{n/2}e^{Cn}. \] Thus the scale $n^{n/2}$, up to exponential factors, is universal for log-concave measures in this high-dimensional exponential regime. Finally, we construct a symmetric isotropic full-support non-log-concave counterexample with only $(1+o(1))2^n$ expected facets.