• search hit 3 of 21
Back to Result List

Low-Dimensional Faces of Random 0/1-Polytopes

Please always quote using this URN:urn:nbn:de:0296-matheon-146
  • Abstract. Let P be a random 0/1-polytope in Rd with n(d) vertices, and denote by νr (P ) the quotient of the number of faces of P with exactly r vertices and n(d) (the r-density of P ). For each r r ≥ 3, we establish the existence of a sharp threshold for the r-density and determine the values of the threshold numbers τr such that, for all ε > 0, E [νr (P )] = 1 − o(1) o(1) if n(d) ≤ 2(τr −ε)d for all d if n(d) ≥ 2(τr +ε)d for all d holds for the expected value of νr (P ). The threshold for r = 2 has already been determined in [8]. In particular, these results indicate that the high densities often encountered in polyhedral com- binatorics (e.g., the cut-polytope has both 2- and 3-density equal to one) is due to the geometry of 0/1-polytopes rather than to the special combinatorics of the underlying problems.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Volker Kaibel
URN:urn:nbn:de:0296-matheon-146
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:8
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.