2026/07/24 by Catherine Babecki, Tycho Elling, Asaf Ferber
Mathematics · #Limits and Structures in Graph Theory #Advanced Combinatorial Mathematics #Graph theory and applications
paper · doi:10.1112/blms.70456
Abstract We study graph‐theoretic properties of random polytopes. Specifically, let be a random subset where each point is included independently with probability , and consider the graph of the polytope . We provide a short and combinatorial proof that is a threshold for when the edge density of is 1, a result originally due to Kaibel and Remshagen. We next resolve an open question from their paper by showing that for , exhibits strong edge expansion. In particular, we prove that, with high probability, every vertex has degree . Lastly, we determine the threshold for being a clique, strengthening a result of Bondarenko and Brodskiy. We show that with high probability, if , then is not a clique, and if , then is a clique, where . Our approach combines a combinatorial characterization of edges in graphs arising from polytopes with the Kim–Vu polynomial concentration inequality.