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 (~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) ≤ (2~(1/2) - ε)~d holds for all large d, while it converges to zero if n(d) ≥ (2~(1/2) + ε)~d holds for all large d.
展开▼
