On the normalized Laplacian spectra of random geometric graphs (Q6042058)

The authors consider random geometric graphs (RGGs) and the spectra of their normalized Laplacian matrices. These random graphs are defined by parameters \(n\), \(d\), \(r_n\), \(p\); and are constructed by sampling \(n\) vertices at random from a \(d\)-dimensional torus, and joining two points if they have \(l_p\) distance at most \(r_n\). The behaviour of such graphs is studied as \(n\) tends to infinity, usually with \(r_n\) tending to zero. The authors focus on two regimes, the ``connectivity regime'' where the average degree of the graphs grows at least logarithmically in \(n\); and the ``thermodynamical regime'', where the average degree is a constant. The main result says that the normalized Laplacian spectra of RGGs are closely related to the normalized Laplacian spectra of some deterministic geometric graph (DGG), which is obtained by placing the points in the torus in an evenly-spaced, grid-like fashion. More precisely, the authors show that the normalized Laplacian matrices of RGGs and DGGs become arbitrarily ``close'' in the Hilbert-Schmidt norm, as \(n\) tends to infinity. The authors get different and more specific qualitative versions of these results, depending on the regime (connectivity, thermodynamical) taken into consideration.