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

DOI10.1214/11-AOP734zbMATH Open1272.05111arXiv1103.1919OpenAlexW3106436031MaRDI QIDQ373567FDOQ373567

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)

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}$.

Full work available at URL: https://arxiv.org/abs/1103.1919

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)

Cites Work

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

Cited In (only showing first 100 items - show all)

• Title not available (Why is that?)
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Quantitative results for banded Toeplitz matrices subject to random and deterministic perturbations
• Spectrum of random d‐regular graphs up to the edge
• Localized phase for the Erdős-Rényi graph
• Spectral gap and edge universality of dense random regular graphs
• Local Marchenko-Pastur law for sparse rectangular random matrices
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• 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
• Local-density dependent Markov processes on graphons with epidemiological applications
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Asymptotic representation theory and the spectrum of a random geometric graph on a compact Lie group
• Bulk eigenvalue fluctuations of sparse random matrices
• Rigidity of eigenvalues for \(\beta\) ensemble in multi-cut regime
• Action convergence of operators and graphs
• Sample canonical correlation coefficients of high-dimensional random vectors with finite rank correlations
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Analysis of the neighborhood pattern similarity measure for the role extraction problem
• Limiting spectral distribution of stochastic block model
• Spectral graph matching and regularized quadratic relaxations. II: Erdős-Rényi graphs and universality
• Universality of the least singular value for the sum of random matrices
• Mesoscopic eigenvalue density correlations of Wigner matrices
• Edge rigidity and universality of random regular graphs of intermediate degree
• Edge universality of separable covariance matrices
• Outliers in spectrum of sparse Wigner matrices
• Sample canonical correlation coefficients of high-dimensional random vectors: Local law and Tracy–Widom limit
• On the spectrum of dense random geometric graphs
• Hitting times, commute times, and cover times for random walks on random hypergraphs
• Estimating Mixed Memberships With Sharp Eigenvector Deviations
• Universality of the least singular value for sparse random matrices
• Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
• The completely delocalized region of the Erdős-Rényi graph
• Diluted banded random matrices: scaling behavior of eigenfunction and spectral properties
• Local laws for sparse sample covariance matrices without the truncation condition
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• Higher order fluctuations of extremal eigenvalues of sparse random matrices
• Optimal delocalization for generalized Wigner matrices
• Optimal multi-resolvent local laws for Wigner matrices
• 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 law and Tracy-Widom limit for sparse sample covariance matrices
• Risk-dependent centrality in economic and financial networks
• Rate of convergence for sparse sample covariance matrices
• A localization-delocalization transition for nonhomogeneous random matrices
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• On Cramér-von Mises statistic for the spectral distribution of random matrices
• Bulk universality of sparse random matrices
• Anisotropic local laws for random matrices
• Local elliptic law
• Noise sensitivity for the top eigenvector of a sparse random matrix
• Local spectral statistics of the addition of random matrices
• Dyson Brownian motion for general \(\beta\) and potential at the edge
• Rigidity and a mesoscopic central limit theorem for Dyson Brownian motion for general \(\beta\) and potentials
• Free energy of bipartite spherical Sherrington-Kirkpatrick model
• On optimal bounds in the local semicircle law under four moment condition
• Spectral statistics of sparse Erdős-Rényi graph Laplacians
• GOE statistics for Lévy matrices
• Delocalization transition for critical Erdős-Rényi graphs
• Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• A necessary and sufficient condition for edge universality of Wigner matrices
• A necessary and sufficient condition for edge universality at the largest singular values of covariance matrices
• Local deformed semicircle law and complete delocalization for Wigner matrices with random potential
• Local law for eigenvalues of random regular bipartite graphs
• Comparison theorem for some extremal eigenvalue statistics
• Local Kesten-McKay law for random regular graphs
• Convergence of local statistics of Dyson Brownian motion
• Averaging fluctuations in resolvents of random band matrices
• Eigenvector statistics of Lévy matrices
• Quantum ergodicity on graphs: from spectral to spatial delocalization
• How much can the eigenvalues of a random Hermitian matrix fluctuate?
• The outliers of a deformed Wigner matrix
• Ferromagnetic to paramagnetic transition in spherical spin glass
• Limiting distribution of the sample canonical correlation coefficients of high-dimensional random vectors
• Bounds for the Stieltjes transform and the density of states of Wigner matrices
• Random band matrices in the delocalized phase. III: Averaging fluctuations
• Eigenvectors of random matrices: A survey
• Isotropic self-consistent equations for mean-field random matrices
• Spherical spin glass model with external field
• Intertwinings of beta-Dyson Brownian motions of different dimensions
• Sparse regular random graphs: spectral density and eigenvectors
• Vertices cannot be hidden from quantum spatial search for almost all random graphs
• Centrality metrics and localization in core-periphery networks
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Exponential growth of random determinants beyond invariance
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• No-gaps delocalization for general random matrices
• Local semicircle law under weak moment conditions
• Delocalization of eigenvectors of random matrices with independent entries
• Recent results of quantum ergodicity on graphs and further investigation
• Universality for random matrix flows with time-dependent density
• Edge universality for deformed Wigner matrices
• Delocalization and diffusion profile for random band matrices
• On high moments of strongly diluted large Wigner random matrices
• Local law and Tracy-Widom limit for sparse stochastic block models
• Delocalization for a class of random block band matrices

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)