TY - GEN A1 - Kaibel, Volker T1 - Low-Dimensional Faces of Random 0/1-Polytopes N2 - 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. Y1 - 2003 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/14 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-146 ER -