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

The distribution RGG(n,Sᵈ⁻¹,p) is formed by sampling independent vectors ᵢ = 1ⁿ uniformly on Sᵈ⁻¹ 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 Erd{o}s-R\'enyi and RGG such that G(n,p(1 - Õ(√np/d)))⊆ RGG(n,Sᵈ⁻¹,p)⊆ G(n,p(1 + Õ(√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{o}s-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ᵈ⁻¹,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 exp(dnlog⁻⁷n), recovering (up to the log factors) the sharp result of Sauermann.