On the Graph-Density of Random 0/1-Polytopes

Let X _d,n be an n-element subset of {0,1}d chosen uniformly at random, and denote by P _d,n : = conv X _d,n its convex hull. Let Δ _d,n be the density of the graph of P _d,n (i.e., the number of one-dimensional faces of P _d,n divided by $\binom{n}{2}$). Our main result is that, for any function n(d), the expected value of Δ _d,n(d) converges (with d→ ∞) to one if, for some arbitrary ε> 0, $n(d)\le (\sqrt{2}-\varepsilon)^d$ holds for all large d, while it converges to zero if $n(d)\ge (\sqrt{2}+\varepsilon)^d$ holds for all large d.