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

Abstract

We study graph‐theoretic properties of random 0/1$0/1$ polytopes. Specifically, let Qpn⊆{0,1}n$Q_p^n \subseteq \lbrace 0,1\rbrace ^n$ be a random subset where each point is included independently with probability p$p$ , and consider the graph Gp$G_p$ of the polytope conv(Qpn)$\operatorname{conv}(Q_p^n)$ . We provide a short and combinatorial proof that p=2−n/2$p = 2^{-n/2}$ is a threshold for when the edge density of Gp$G_p$ is 1, 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)$p \leqslant 2^{-n/2 - o(1)}$ , Gp$G_p$ exhibits strong edge expansion. In particular, we prove that, with high probability, every vertex has degree (1−o(1))|Qpn|$(1 - o(1))|Q_p^n|$ . Lastly, we determine the threshold for Gp$G_p$ being a clique, strengthening a result of Bondarenko and Brodskiy. We show that with high probability, if p⩾2−δn+o(1)$ p \geqslant 2^{-\delta n + o(1)}$ , then Gp$G_p$ is not a clique, and if p⩽2−δn−o(1)$ p \leqslant 2^{-\delta n - o(1)}$ , then Gp$G_p$ is a clique, where δ≈0.8295$\delta \approx 0.8295$ . Our approach combines a combinatorial characterization of edges in graphs arising from polytopes with the Kim–Vu polynomial concentration inequality.