On the Graph-Density of Random 0/1-Polytopes
Please always quote using this URN:urn:nbn:de:0296-matheon-136
- Abstract. Let Xd,n be an n-element subset of {0, 1}d chosen uniformly at random, and denote by Pd,n := conv Xd,n its convex hull. Let ∆d,n be the density of the graph of Pd,n (i.e., the number of one-dimensional faces of Pd,n divided by n ). Our main result is that, for any function 2 n(d), the expected value of ∆d,n(d) converges (with d → ∞) to one if, √ for some arbitrary ε < 0, n(d) ≤ ( 2 − ε)d holds for all large d, while it √ converges to zero if n(d) ≥ ( 2 + ε)d holds for all large d.
Author: | Volker Kaibel, Anja Remshagen |
---|---|
URN: | urn:nbn:de:0296-matheon-136 |
Referee: | Günter M. Ziegler |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2003/12/15 |
Release Date: | 2003/12/15 |
Preprint Number: | 7 |