Premium
A Large Deviations Approach to the Geometry of Random Polytopes
Author(s) -
Gatzouras D.,
Giannopoulos A.
Publication year - 2006
Publication title -
mathematika
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.955
H-Index - 29
eISSN - 2041-7942
pISSN - 0025-5793
DOI - 10.1112/s0025579300000097
Subject(s) - mathematics , citation , polytope , combinatorics , library science , mathematics education , computer science
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 }