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

Kiril Bangachev, Guy Bresler

The distribution $\mathsf{RGG}(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 pair…