The geometry of random \(\{-1,1\}\)-polytopes (Q2572591): Difference between revisions

Let \(n\) and \(N\) be positive integers and \((\omega _{i,j})\), \(1\leq i\leq n\), \(1\leq j\leq N\), be independent copies of a symmetric \(\{-1,1\}\)-valued random variable \(\omega\). If \(e_1, e_2, \ldots, e_n\) denote the standard basis of \(\mathbb R^n\), each \(X_i=\sum _{j=1}^n \omega_{i,j}e_j\) is a random point in the cube \(\{-1,1\}^n\). One defines a random \(\{-1,1\}\)-polytope by \(K_{n,N}=\text{conv} (\pm X_1,\ldots, \pm X_N)\). One says that a certain property is satisfied by a random polytope if the set of polytopes \(K_{n,N}\) satisfying this property has probability larger than \(1-c^n\), where \(c\) is a numerical constant \(0<c<1\) which is independent of \(n\) and \(N\). The authors focus on three geometric characteristics associated to a polytope: the combinatorial dimension (which measures the tradeoff between the size of a cube contained in a coordinate projection of a set and the dimension of the projection), the entropy and the Gelfand numbers (the \(k\)th Gelfand number of a body \(K\) is half of the smallest diameter of a \((k-1)\)-codimensional section of \(K\)). The main results show that for \(2n\leq N\leq 2^n\), the upper bounds for these parameters that hold for any polytope \(K_{n,N}\) are attained by random polytopes at every scale of the parameter in question. The proofs make heavily use of many previous results.