On 0-1 polytopes with many facets (Q5945246)

Let \(Z_1,\dots,Z_n\) be \(n\) independent random variables distributed uniformly over \(\{-1,1\}\). Set \(\underline Z=(Z_1, \dots,Z_n)\). Thus \(\underline Z\) is uniformly distributed over the \(2^n\) vertices of the \(n\)-dimensional \(\pm 1\) cube. Consider \(N\) independent copies \(\underline Z_1,\dots, \underline Z_N\) of \(\underline Z\) and define the random \(0-1\) polytope on \(N\) vertices to be NEWLINE\[NEWLINEK_n=\text{conv}\{\underline Z_1,\dots, \underline Z_N\}.NEWLINE\]NEWLINE Assuming the condition NEWLINE\[NEWLINE\exp\bigl\{ c_4(\log n)^2\bigr\} <N<\exp \left(c_5 {n \over\log n} \right)NEWLINE\]NEWLINE with \(c_4\leq 1\) and \(c_5\geq 1\) the authors prove the following two results:NEWLINENEWLINENEWLINE\(\bullet\) \(E[f_{n-1} (K_N)]>(c_6\log N)^{n\over 4}\) (where \(E[f_{n-1}(K_N)]\) is the expected number of facets);NEWLINENEWLINENEWLINE\(\bullet\) there exists a polytope \(K_N\) with \(f_{n-1}(K_N) >(c_7\log N)^{n\over 4}\).