When is the graph of a random 0/1 polytope a clique?

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.