• search hit 2 of 21
Back to Result List

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
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
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.