On the spectrum of dense random geometric graphs (Q2170358)

Let \(G\) be an \(n\)-vertex undirected graph, and let \(A\) be its adjacency matrix. The degree of the vertex \(i\) is then \(d_i=|N_G(i)|\), the number of neighbours of vertex \(i\) in \(G\), and the Laplacian of \(G\) is defined as \(L:=D-A\), where \(D\) is the diagonal matrix of vertex degrees. The normalized graph Laplacian of \(G\) is defined as \[ \mathcal{L}:=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}. \] Graph Laplacians and their spectra contain important information about the connectivity structure of graphs and the behavior of random walks on them. Graph spectra and harmonics also play key roles in various applications such as network analysis and machine learning. The random geometric graph \(G(n,r)\) is defined as the undirected graph with vertex set \(\{1,2,\ldots,n\}\), where \(i\) is adjacent to \(j\), if, and only if, \(\|X_i - X_j\|\leq r\), where \(\|\cdot\|\) denotes the norm in \(\mathbb{R}^d\). In this paper, the authors study the spectrum of the random geometric graph \(G(n,r)\), in a regime where the graph is dense and highly connected. In the Erdös-Rényi random graph \(G(n,p)\), it is well known that upon connectivity the spectrum of the normalized graph Laplacian is concentrated around 1. The authors show that such concentration does not occur in the \(G(n,r)\) case, even when the graph is dense and almost complete. They also show that the limiting spectral gap is strictly smaller than \(1\). In the special case where the vertices are distributed uniformly in the unit cube and \(r = 1\), they prove that for all \(k\in [0,d]\) there exists at least \(\binom{d}{k}\) eigenvalues near \(1-2^{-k}\), and the limiting spectral gap is exactly 1/2. They confirm that the corresponding eigenfunctions in this case are tightly related to the geometric configuration of the points. The study of this paper has a nice motivation and the results obtained in this paper are interesting.