Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs

DOI10.1214/19-AOP1339MaRDI QIDQ2280557zbMATH OpenOpenAlexFDO

Authors Yukun He, Antti Knowles, Matteo Marcozzi

Publication date 18 December 2019

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

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

zbMATH Keywords

eigenvector delocalizationErdős-Rényi graphlocal lawsparse random matrix

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: We prove a local law for the adjacency matrix of the ErdH{o}s-R'enyi graph $G(N,p)$ in the supercritical regime $pNgeqClogN$ where $G(N,p)$ has with high probability no isolated vertices. In the same regime, we also prove the complete delocalization of the eigenvectors. Both results are false in the complementary subcritical regime. Our result improves the corresponding results from [11] by extending them all the way down to the critical scale $pN=O(logN)$. A key ingredient of our proof is a new family of multilinear large deviation estimates for sparse random vectors, which carefully balance mixed $el{l}^2$ and $el{l}^{i}nfty$ norms of the coefficients with combinatorial factors, allowing us to prove strong enough concentration down to the critical scale $pN=O(logN)$. These estimates are of independent interest and we expect them to be more generally useful in the analysis of very sparse random matrices.

Recommendations

• The completely delocalized region of the Erdős-Rényi graph
• Delocalization transition for critical Erdős-Rényi graphs
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Sparse random graphs: eigenvalues and eigenvectors
• Spectral statistics of sparse Erdős-Rényi graph Laplacians

Cites work

• Bulk universality for generalized Wigner matrices
• Bulk universality of sparse random matrices
• Delocalization and diffusion profile for random band matrices
• Isotropic self-consistent equations for mean-field random matrices
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Local Kesten-McKay law for random regular graphs
• Local law and Tracy-Widom limit for sparse random matrices
• Local semicircle law and complete delocalization for Wigner random matrices
• Local semicircle law for random regular graphs
• Local semicircle law for Wigner matrices
• Mesoscopic eigenvalue statistics of Wigner matrices
• Quadratic vector equations on complex upper half-plane
• Random graphs and complex networks. Volume 1
• Semicircle law on short scales and delocalization of eigenvectors for Wigner random matrices
• Sparse general Wigner-type matrices: local law and eigenvector delocalization
• Sparse random graphs: eigenvalues and eigenvectors
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Transition from Tracy-Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős-Rényi graphs
• Universality for general Wigner-type matrices

Cited in

(19)

• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• The completely delocalized region of the Erdős-Rényi graph
• Quantitative results for banded Toeplitz matrices subject to random and deterministic perturbations
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Noise sensitivity for the top eigenvector of a sparse random matrix
• Edge rigidity and universality of random regular graphs of intermediate degree
• Bulk eigenvalue fluctuations of sparse random matrices
• Delocalization transition for critical Erdős-Rényi graphs
• Universality of the least singular value for sparse random matrices
• 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
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Sparse Hanson-Wright inequalities with applications
• Large deviations of the largest eigenvalue of supercritical sparse Wigner matrices
• Phase transition for the bottom singular vector of rectangular random matrices
• Limit results for estimation of connectivity matrix in multi-layer stochastic block models
• Sparse graph signals -- uncertainty principles and recovery
• Convergence of the density of states and delocalization of eigenvectors on random regular graphs

This page was built for publication: Local law and complete eigenvector delocalization for supercritical Erdős-Rényi graphs

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