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

The distribution $\mathsf{R}\mathsf{G}\mathsf{G}(n,{\mathbb{S}}^{d-1},p)$ is formed by sampling independent vectors $\{V_i{\}}_{i=1}^n$ uniformly on ${\mathbb{S}}^{d-1}$ and placing an edge between pairs of vertices $i$ and $j$ for which $⟨V_i,V_j⟩\ge {\tau }_d^p,$ where ${\tau }_d^p$ is such that the expected density is $p\mathrm{.}$ Our main result is a poly-time implementable coupling between Erdős-Rényi and $\mathsf{R}\mathsf{G}\mathsf{G}$ such that $\mathsf{G}(n,p(1-\tilde{O}(\sqrt{np\mathrm{/}d})))\subseteq \mathsf{R}\mathsf{G}\mathsf{G}(n,{\mathbb{S}}^{d-1},p)\subseteq \mathsf{G}(n,p(1+\tilde{O}(\sqrt{np\mathrm{/}d})))$ edgewise with high probability when $d\gg np\mathrm{.}$ 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 $p_n^c,$ random geometric graphs also exhibit a sharp threshold when $d\gg n{p}_n^c,$ thus partially answering a question of Perkins. 2) Robust Testing: The coupling shows that testing between $\mathsf{G}(n,p)$ and $\mathsf{R}\mathsf{G}\mathsf{G}(n,{\mathbb{S}}^{d-1},p)$ with $\epsilon n^{2}p$ adversarially corrupted edges for any constant $\epsilon >0$ is information-theoretically impossible when $d\gg np\mathrm{.}$ We match this lower bound with an efficient (constant degree SoS) spectral refutation algorithm when $d\ll np\mathrm{.}$ 3) Enumeration: We show that the number of geometric graphs in dimension $d$ is at least $\exp (dn{\log }^{-7}n)$, recovering (up to the log factors) the sharp result of Sauermann.