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.
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 |