Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration

Abstract

The distribution RGG(n,Sd−1,p) is formed by sampling independent vectors {Vi}i = 1n uniformly on Sd−1 and placing an edge between pairs of vertices i and j for which ⟨ Vi,Vj⟩ ≥ τdp, where τdp is such that the expected density is p. Our main result is a poly-time implementable coupling between Erdős-Rényi and RGG such that G(n,p(1 − O(√np/d)))⊆ RGG(n,Sd−1,p)⊆ G(n,p(1 + O(√np/d))) edgewise with high probability when d≫ np. We apply the result to: 1) Sharp Thresholds: We show that for any monotone property having a sharp threshold with respect to the Erdős-Rényi distribution and critical probability pnc, random geometric graphs also exhibit a sharp threshold when d≫ npnc, thus partially answering a question of Perkins. 2) Robust Testing: The coupling shows that testing between G(n,p) and RGG(n,Sd−1,p) with є n2p adversarially corrupted edges for any constant є>0 is information-theoretically impossible when d≫ np. We match this lower bound with an efficient (constant degree SoS) spectral refutation algorithm when d≪ np. 3) Enumeration: We show that the number of geometric graphs in dimension d is at least exp(dnlog−7n), recovering (up to the log factors) the sharp result of Sauermann.