2025/07/03 by Babecki, Catherine, Elling, Tycho, Ferber, Asaf
#05C75 #05D40 #52B05 #52B12 #60C05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.03212
We study graph-theoretic properties of random 0/1 polytopes. Specifically, let Qpn ⊆ \0,1\n be a random subset where each point is included independently with probability p, and consider the graph Gp of the polytope conv(Qpn). We provide a short and combinatorial proof that p = 2-n/2 is a threshold for the edge density of Gp, a result originally due to Kaibel and Remshagen. We next resolve an open question from their paper by showing that for p ≤ 2-n/2 - o(1), Gp exhibits strong edge expansion. In particular, we prove that, with high probability, every vertex has degree (1 - o(1))|Qpn|. Lastly, we determine the threshold for Gp being a clique, strengthening a result of Bondarenko and Brodskiy. We show that with high probability, if p ≥ 2-δn + o(1), then Gp is not a clique, and if p ≤ 2-δn - o(1), then Gp is a clique, where δ≈ 0.8295. Our approach combines a combinatorial characterization of edges in graphs arising from polytopes with the Kim-Vu polynomial concentration inequality.