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

Source 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 $μ$ be a non-degenerate compactly supported even probability measure on $\R$ satisfying $μ([x^\ast-s,x^\ast])\asymp s^κ$ near its right endpoint $x^\ast$. For every sufficiently small fixed $α>0$, the convex hull of $N=\lfloor e^{αn}\rfloor$ independent points with law $μ^{\otimes n}$ has at least $n^{n/2}e^{-C_{μ,α}n}$ expected facets; this includes all symmetric finite-alphabet distributions. For every full-dimensional log-concave probability measure on $\R^n$, we prove that there exist $T\in[n,2n]$ and $N=\lceil e^Tn^{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.