Low-Dimensional Faces of Random 0/1-Polytopes

Let P be a random 0/1-polytope in ℝd with n(d) vertices, and denote by ϕ _k (P) the k-face density of P, i.e., the quotient of the number of k-dimensional faces of P and $\binom{n(d)}{k+1}$. For each k≥ 2, we establish the existence of a sharp threshold for the k-face density and determine the values of the threshold numbers τ _k such that, for all ε> 0, $$ {\mathbb{E}}[\varphi_k(P)]\ =\ \begin{cases} 1-{\mathrm o}(1) & \text{ if $n(d)\le 2^{(\tau_k-\varepsilon)d}$ for all~$d$} \\ {\mathrm o}(1) & \text{ if $n(d)\ge 2^{(\tau_k+\varepsilon)d}$ for all~$d$} \\ \end{cases} $$ holds for the expected value of ϕ _k (P). The threshold for k=1 has recently been determined in [1].In particular, these results indicate that the high face densities often encountered in polyhedral combinatorics (e.g., for the cut-polytopes of complete graphs) should be considered more as a phenomenon of the general geometry of 0/1-polytopes than as a feature of the special combinatorics of the underlying problems.