Skip to main content
3 of 4
added 98 characters in body
Carlo Beenakker
  • 188.2k
  • 18
  • 448
  • 651

For $N_\lambda$ denoting the number of eigenvalues less than $\lambda$, Weyl's law gives the asymptotics of $N_\lambda$ as $\lambda$ tends to infinity. The usual approach to establish this asymptotics in the continuum divides space into boxes. This fails for a graph, since cutting the graph is not a small perturbation.
An analogue of Weyl asymptotics for graph Laplacians that satisfy a strong isoperimetric inequality is given in Graphs and Discrete Dirichlet Spaces by Keller, Lenz, and Wojciechowski, page 439. See also Essential spectrum and Weyl asymptotics for discrete Laplacians by Bonnefont and Golenia.

The above refers to the eigenvalues. For the eigenvectors, the localisation phenomenon has been studied in Localization of Laplacian eigenvectors on random networks, but there is no "rigorous" theory.


Concerning the connection with random matrix theory: Randomly weighted graphs [fixed number of neighbors $d$ of each vertex, with weights defined on the edges that are uniformly and independently drawn from (-1,1)] have a mean spectral density $\rho(\mu)$ of the graph Laplacian given by the Kesten-McCay law $$\rho(\mu)=\frac{d}{2\pi}(d^2-\mu^2)^{-1}\sqrt{4(d-1)-\mu^2},\;\;\text{for}\;\;|\mu|<2\sqrt{d-1}.$$ See for example Local Kesten-McKay law for random regular graphs. In this case the eigenvalues are delocalised. The Wigner semi-circle law of Gaussian random matrix ensembles is obtained in the limit $d\rightarrow\infty$.

Carlo Beenakker
  • 188.2k
  • 18
  • 448
  • 651