Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law

DOI10.1214/11-AOP734MaRDI QIDQ373567zbMATH OpenOpenAlexFDO

Authors László Erdős, Antti Knowles, Horng-Tzer Yau, Jun Yin

Publication date 17 October 2013

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1103.1919, https://projecteuclid.org/euclid.aop/1368623526

zbMATH Keywords

random graphsdensity of statesadjacency matriceslocal semicircle lawErdős-Rényi graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: We consider the ensemble of adjacency matrices of ErdH{o}s-R'{e}nyi random graphs, that is, graphs on $N$ vertices where every edge is chosen independently and with probability $pequivp(N)$. We rescale the matrix so that its bulk eigenvalues are of order one. We prove that, as long as $pNoinfty$ (with a speed at least logarithmic in $N$), the density of eigenvalues of the ErdH{o}s-R'{e}nyi ensemble is given by the Wigner semicircle law for spectral windows of length larger than $N^{-1}$ (up to logarithmic corrections). As a consequence, all eigenvectors are proved to be completely delocalized in the sense that the $el{l}^{infty}$-norms of the $el{l}^2$-normalized eigenvectors are at most of order $N^{-1/2}$ with a very high probability. The estimates in this paper will be used in the companion paper [Spectral statistics of ErdH{o}s-R'{e}nyi graphs II: Eigenvalue spacing and the extreme eigenvalues (2011) Preprint] to prove the universality of eigenvalue distributions both in the bulk and at the spectral edges under the further restriction that $pNgg{N}^{2/3}$.

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 51346 (Why is no real title available?)
• scientific article; zbMATH DE number 1464566 (Why is no real title available?)
• A Brownian-Motion Model for the Eigenvalues of a Random Matrix
• A refinement of Wigner's semicircle law in a neighborhood of the spectrum edge for random symmetric matrices
• An introduction to random matrices
• Bulk universality and related properties of Hermitian matrix models
• Bulk universality for Wigner matrices
• Bulk universality for generalized Wigner matrices
• Characteristic vectors of bordered matrices with infinite dimensions
• Concentration of the spectral measure for large matrices
• Convergence rates of the spectral distributions of large Wigner matrices
• Eigenvectors of random graphs: nodal domains
• Large random matrices: Lectures on macroscopic asymptotics. École d'Été des Probabilités de Saint-Flour XXXVI -- 2006
• Local semicircle law and complete delocalization for Wigner random matrices
• On finite rank deformations of Wigner matrices
• Orthogonal polynomials and random matrices: a Riemann-Hilbert approach.
• Random matrices: Universality of local eigenvalue statistics up to the edge
• Random matrices: universality of local eigenvalue statistics
• Random matrix theory. Invariant ensembles and universality
• Rigidity of eigenvalues of generalized Wigner matrices
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Semiclassical asymptotics of orthogonal polynomials, Riemann-Hilbert problem, and universality in the matrix model
• Sparse random graphs: eigenvalues and eigenvectors
• Sparse regular random graphs: spectral density and eigenvectors
• Spectral norm of random matrices
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Sur la loi limite de l'espacement des valeurs propres d'une matrice ale´atoire
• The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
• The largest eigenvalue of rank one deformation of large Wigner matrices
• The largest eigenvalues of finite rank deformation of large Wigner matrices: Convergence and nonuniversality of the fluctuations
• The local relaxation flow approach to universality of the local statistics for random matrices
• The spectral edge of some random band matrices
• Uniform asymptotics for polynomials orthogonal with respect to varying exponential weights and applications to universality questions in random matrix theory
• Universality at the edge of the spectrum in Wigner random matrices.
• Universality for generalized Wigner matrices with Bernoulli distribution
• Universality of random matrices and local relaxation flow
• Universality of sine-kernel for Wigner matrices with a small Gaussian perturbation
• Wegner Estimate and Level Repulsion for Wigner Random Matrices

Cited in

(only showing first 100 items - show all)

• Correlated random matrices: band rigidity and edge universality
• Exponential growth of random determinants beyond invariance
• On optimal bounds in the local semicircle law under four moment condition
• Fixed energy universality of Dyson Brownian motion
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• Overlaps of a spherical spin glass model with microscopic external field
• Recent results of quantum ergodicity on graphs and further investigation
• Local law and Tracy-Widom limit for sparse stochastic block models
• Universality for random matrix flows with time-dependent density
• Limiting distribution of the sample canonical correlation coefficients of high-dimensional random vectors
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• Bulk universality of sparse random matrices
• Extremal eigenvalues and eigenvectors of deformed Wigner matrices
• How much can the eigenvalues of a random Hermitian matrix fluctuate?
• Convergence of local statistics of Dyson Brownian motion
• Spherical spin glass model with external field
• GOE statistics for Lévy matrices
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• A necessary and sufficient condition for edge universality of Wigner matrices
• Edge universality of correlation matrices
• Local semicircle law under fourth moment condition
• A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices
• Local law for eigenvalues of random regular bipartite graphs
• Bulk universality for generalized Wigner matrices with few moments
• Delocalization and diffusion profile for random band matrices
• Bounds for the Stieltjes transform and the density of states of Wigner matrices
• Intertwinings of beta-Dyson Brownian motions of different dimensions
• Sparse regular random graphs: spectral density and eigenvectors
• Delocalization transition for critical Erdős-Rényi graphs
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Rigidity and a mesoscopic central limit theorem for Dyson Brownian motion for general \(\beta\) and potentials
• Eigenvectors of random matrices: A survey
• The outliers of a deformed Wigner matrix
• Local semicircle law under moment conditions: the Stieltjes transform, rigidity, and delocalization
• Anisotropic local laws for random matrices
• Local elliptic law
• Noise sensitivity for the top eigenvector of a sparse random matrix
• Delocalization for a class of random block band matrices
• On the largest and the smallest singular value of sparse rectangular random matrices
• On high moments of strongly diluted large Wigner random matrices
• Local deformed semicircle law and complete delocalization for Wigner matrices with random potential
• Random band matrices in the delocalized phase. III: Averaging fluctuations
• A goodness-of-fit test for stochastic block models
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• Isotropic self-consistent equations for mean-field random matrices
• Delocalization and limiting spectral distribution of Erdős-Rényi graphs with constant expected degree
• Centrality metrics and localization in core-periphery networks
• Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs
• Ferromagnetic to paramagnetic transition in spherical spin glass
• Comparison theorem for some extremal eigenvalue statistics
• Large deviation theorem for zeros of polynomials and Hermitian random matrices
• Local law and Tracy-Widom limit for sparse random matrices
• Local spectral statistics of the addition of random matrices
• No-gaps delocalization for general random matrices
• Random perturbations of matrix polynomials
• Local Kesten-McKay law for random regular graphs
• A local limit law for the empirical spectral distribution of the anticommutator of independent Wigner matrices
• Averaging fluctuations in resolvents of random band matrices
• Local semicircle law under weak moment conditions
• Dyson Brownian motion for general \(\beta\) and potential at the edge
• Edge universality for deformed Wigner matrices
• Universality of covariance matrices
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Delocalization of eigenvectors of random matrices with independent entries
• Free energy of bipartite spherical Sherrington-Kirkpatrick model
• Delocalization at small energy for heavy-tailed random matrices
• Eigenvector statistics of Lévy matrices
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• Diluted banded random matrices: scaling behavior of eigenfunction and spectral properties
• Local Marchenko-Pastur law for sparse rectangular random matrices
• Universality of the least singular value for the sum of random matrices
• Edge universality of separable covariance matrices
• Local law and Tracy-Widom limit for sparse sample covariance matrices
• Local laws for sparse sample covariance matrices without the truncation condition
• Outliers in spectrum of sparse Wigner matrices
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• Mesoscopic eigenvalue density correlations of Wigner matrices
• Bulk eigenvalue fluctuations of sparse random matrices
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Sample canonical correlation coefficients of high-dimensional random vectors: Local law and Tracy–Widom limit
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• Spectrum of random d‐regular graphs up to the edge
• Localized phase for the Erdős-Rényi graph
• Tail bounds for gaps between eigenvalues of sparse random matrices
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Edge statistics of large dimensional deformed rectangular matrices
• Local-density dependent Markov processes on graphons with epidemiological applications
• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Higher order fluctuations of extremal eigenvalues of sparse random matrices
• Rigidity of eigenvalues for \(\beta\) ensemble in multi-cut regime
• Edge rigidity and universality of random regular graphs of intermediate degree
• Spectral gap and edge universality of dense random regular graphs

This page was built for publication: Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q373567)