A Large Deviations Approach to the Geometry of Random Polytopes

The aim of this article is to present a general “large deviations approach” to the geometry of polytopes spanned by random points with independent coordinates. The origin of our work is in the study of the structure of ±1-polytopes, the convex hulls of subsets of the combinatorial cube E 2 = {−1, 1}n. Understanding the complexity of this class of polytopes is important for the “polyhedral combinatorics” approach to combinatorial optimization, and was put forward by Ziegler in [20]. Many natural questions regarding the behavior of ±1–polytopes in high dimensions are open, since, for many important geometric parameters, low-dimensional intuition does not help to identify the extremal ±1-polytopes. The study of random ±1-polytopes sheds light to some of these questions, the main reason being that random behavior is often the extremal one. A natural way to define random ±1-polytopes is to fix N > n and to consider N independent random points ~ X1, . . . , ~ XN , uniformly distributed over E n 2 . Let Kn,N = conv { ± ~ X1, . . . ,± ~ XN }