Sparse regular random graphs: Spectral density and eigenvectors

By Ioana Dumitriu, Soumik Pal. 2009

106 citations recorded by the source corpus.

We examine the empirical distribution of the eigenvalues and the eigenvectors of adjacency matrices of sparse regular random graphs. We find that when the degree sequence of the graph slowly increases to infinity with the number of vertices, the empirical spectral distribution converges to the semicircle law. Moreover, we prove concentration estimates on the number of eigenvalues over progressively smaller intervals. We also show that, with high probability, all the eigenvectors are delocalized.

View Paper: https://www.semanticscholar.org/paper/0fefa4230d0024abd7468d6d7acc10d0a6f44053

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Size biased couplings and the spectral gap for random regular graphs (2015, result): “The argument in [8] relied on the local semicircle law for uniform random regular graphs, which was established in [9] for the range log4 n ≤ d ≤ n2/3/ log4/3 n, improving on earlier results in [24, 52].”
Localization and delocalization of eigenvectors for heavy-tailed random matrices (2012, background): “In the related model of the adjacency matrix of uniformly sampled d-regular graphs on n vertices, the delocalization of eigenvectors has been studied in Dumitriu and Pal [14] and Tran et al.”
Spectral statistics of Erdős–Rényi graphs I: Local semicircle law (2011, result): “esult shows that the bound conjectured in [10] holds even for p > (logN)CN−1. It was recently proved in [38] that kvαk∞ 6(pN)−1/2 away from the spectral edge; some earlier results were obtained in [11]. These results established only the lower bound pN on the localization length; the complete del”
The spectral gap of dense random regular graphs (2016, result): “Regarding the empirical spectral distribution, we refer, among others, to a classical result of McKay [21], as well as more recent papers [14, 27, 4].”
On the singularity of adjacency matrices for random regular digraphs (2014, methodology): “the Marchenko-Pastur and semi-circular laws were also obtained in [15] and [14] for the sparse regime ω(1) ≤ d ≤ no(1), using the fact that d-regular graphs converge locally (in a quantitative Benjamini-Schramm sense) to d-regular trees.”
Vertex-Frequency Analysis on Graphs (2013, background): “For diﬀerent classes of random graphs, [13, 14, 15] show that with high probability for graphs of suﬃciently large size, the eigenvectors of the graph Laplacian (or in some cases, the graph adjacency operator), are delocalized; i.e., the restriction of the eigenvector to a large set must have…”
Global and Local Uncertainty Principles for Signals on Graphs (2016, background): “For certain classes of random graphs [50, 51, 52] or large regular graphs [53], the eigenvectors have been shown to be non-localized, globally oscillating functions (i.”
Adjacency matrices of random digraphs: singularity and anti-concentration (2015, background): “Among others, we refer the reader to [2], [3], [12], [14], [26], and [35] for results dealing with the eigenvalue distribution.”