Spectra of high-dimensional sparse random geometric graphs

Abstract

We determine the limiting empirical spectral distribution of sparse high-dimensional random geometric graphs. The vertices are independent uniform points on the unit sphere $S^{d-1}$, and two vertices are joined when their inner product exceeds a threshold chosen to give edge density $p$. The edges therefore have the same marginal probabilities as in an Erdős--Rényi graph, but the latent geometry introduces dependence among them. We show that these correlations are asymptotically invisible to the global spectrum in two sparse regimes. If $p\to 0$, $np\to \infty$, and $d=\hat{I}\text{c◯}(np\log (1/p))$, then the empirical spectral distribution of $A/\sqrt{np}$ converges in probability to the semicircle law. If $p=\hat{I}\pm /n$ for a fixed $\hat{I}\pm >0$ and $d=\ddot{I}‰(\log n)$, then the empirical spectral distribution of $A/\sqrt{\hat{I}}\pm$ converges in probability to the limiting spectral distribution of $\mathcal{G}(n,\hat{I}\pm /n)$. The proof combines the moment method with a cluster expansion that decomposes geometric dependence into weak local interactions, allowing us to control every fixed walk pattern in the moment calculation.

39 pages, 1 figure. Major revision. The proof of the global law has been substantially revised using a new argument, leading to an improved result

Topics & keywords