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

The distribution RGG (n, S^d-1, p) is formed by sampling independent vectors \Vᵢ\₈ = ₁ⁿ uniformly on S^d-1 and placing an edge between pairs of vertices i and j for which Vᵢ, Vⱼ ᵖd, where ᵖd is such that the expected density is p. Our main result is a poly-time implementable coupling between Erdos-R\'enyi and RGG such that G (n, p (1 - O (np/d) ) ) RGG (n, S^d-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 Erdos-R\'enyi distribution and critical probability pᶜₙ, random geometric graphs also exhibit a sharp threshold when d npᶜₙ, thus partially answering a question of Perkins. 2) Robust Testing: The coupling shows that testing between G (n, p) and RGG (n, S^d-1, p) with n²p 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 (dn^-7n), recovering (up to the log factors) the sharp result of Sauermann.