The Spectrum of Dense Random Geometric Graphs

Abstract:  We study the spectrum of a random geometric graph, in a regime where the graph is dense and highly connected. As opposed to other random graph models (e.g.~the Erdos-Renyi random graph),  even when the graph is dense, not all the eigenvalues are concentrated around 1. In the case where the vertices are generated uniformly in a unit d-dimensional box, we show that for every \(0\le k \le d\) there are \(\binom{d}{k}\) eigenvalues at \(1-2^{-k}\). The rest of the eigenvalues are indeed close to 1. The spectrum of the graph Laplacian plays a key role in both theory and applications. We also show that the corresponding eigenfunctions are tightly related to the geometric configuration of the points. Aside from the interesting mathematical phenomenon we reveal here, the results of this paper can also be used to analyze the homology of the random Vietoris-Rips complex via spectral methods.