On the graph-density of random 0/1-polytopes

2003/06/17 by Volker Kaibel, Kaibel, Volker, Anja Remshagen +1 · 1 citation
Computer Science · Mathematics · #52B05 #52B12 #60C05 #90C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #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/0306246

11 pages, to appear in: Proceedings of RANDOM03 (Princeton Univ., Aug 24 - Aug 26, 2003)

arxiv created 2003/06/17 · openalex publication_date 2003/06/17 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let X_d,n be an n-element subset of 0,1^d chosen uniformly at random, and denote by P_d,n := conv X_d,n its convex hull. Let D_d,n be the density of the graph of P_d,n (i.e., the number of one-dimensional faces of P_d,n divided by n(n-1)/2). Our main result is that, for any function n(d), the expected value of D_d,n(d) converges (with d tending to infinity) to one if, for some arbitrary e > 0, n(d) <= (√(2)-e)^d holds for all large d, while it converges to zero if n(d) >= (√(2)+e)^d holds for all large d.

Citations

• On the Expansion of Graphs of 0/1-Polytopes

Cited by

• Sharp Threshold for Cliques in Random 0/1 Polytope Graphs

Related

• On the edge expansion of random polytopes
• Low-dimensional faces of random 0/1-polytopes
• Limit theorems for random polytopes with vertices on convex surfaces
• Sharp Threshold for Cliques in Random 0/1 Polytope Graphs
• Expected intrinsic volumes and facet numbers of random beta-polytopes