2003/11/21 by Volker Kaibel, Kaibel, Volker
Computer Science · Mathematics · #52B05 #52B12 #60C05 #90C57 #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #Optimization and Control (math.OC) #Point processes and geometric inequalities #Probability (math.PR) #math.CO #math.OC #math.PR #msc:52B05 #msc:52B12 #msc:60C05 #msc:90C57
paper · pdf · doi:10.48550/arxiv.math/0311393
15 pages, to appear in: Proceedings IPCO X, Jun 9-11, 2004, Columbia University, New York. Changes in the revised version: Slightly improved main result, several minor changes in the presentation, appendix removed
openalex publication_date 2003/11/21 · arxiv created 2004/02/25 · arxiv updated 2009/12/01 · openalex created_date 2016/07/22 · openalex updated_date 2026/07/28
Let P be a random d-dimensional 0/1-polytope with n(d) vertices, and denote by ϕk(P) the k-face density of P, i.e., the quotient of the number of k-dimensional faces of P and \binomn(d)k+1. For each k≥ 2, we establish the existence of a sharp threshold for the k-face density and determine the values of the threshold numbers τk such that, for all ε>0, E(ϕk(P)) = \begincases 1-o(1) amp; \textif n(d)≤ 2(τk-ε)d for all d o(1) amp; \textif n(d)≥ 2(τk+ε)d for all d \endcases holds for the expected value of ϕk(P). The threshold for k=1 has recently been determined in math.CO/0306246. In particular, these results indicate that the high face densities often encountered in polyhedral combinatorics (e.g., for the cut-polytopes of complete graphs) should be considered more as a phenomenon of the general geometry of 0/1-polytopes than as a feature of the special combinatorics of the underlying problems.