Extremal eigenvalues of critical Erdős-Rényi graphs

DOI10.1214/20-AOP1483zbMATH Open1467.05236arXiv1905.03243OpenAlexW3140937560MaRDI QIDQ2039437FDOQ2039437

Authors: Johannes Alt, Antti Knowles, Raphael Ducatez 

Publication date: 2 July 2021

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

Abstract: We complete the analysis of the extremal eigenvalues of the the adjacency matrix $A$ of the ErdH{o}s-R'enyi graph $G(N,d/N)$ in the critical regime $dasymplogN$ of the transition uncovered in [arXiv:1704.02953,arXiv:1704.02945], where the regimes $dgglogN$ and $dlllogN$ were studied. We establish a one-to-one correspondence between vertices of degree at least $2d$ and nontrivial (excluding the trivial top eigenvalue) eigenvalues of $A/sqrtd$ outside of the asymptotic bulk $[-2,2]$. This correspondence implies that the transition characterized by the appearance of the eigenvalues outside of the asymptotic bulk takes place at the critical value $d=d_{\ast }=frac1log4-1logN$. For $d<d_{\ast }$ we obtain rigidity bounds on the locations of all eigenvalues outside the interval $[-2,2]$, and for $d>d_{\ast }$ we show that no such eigenvalues exist. All of our estimates are quantitative with polynomial error probabilities. Our proof is based on a tridiagonal representation of the adjacency matrix and on a detailed analysis of the geometry of the neighbourhood of the large degree vertices. An important ingredient in our estimates is a matrix inequality obtained via the associated nonbacktracking matrix and an Ihara-Bass formula [arXiv:1704.02945]. Our argument also applies to sparse Wigner matrices, defined as the Hadamard product of $A$ and a Wigner matrix, in which case the role of the degrees is replaced by the squares of the $el{l}^2$-norms of the rows.

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

Recommendations

• Eigenvalues and extremal degrees of graphs
• On extremal eigenvalues of the graph Laplacian ^*
• Extreme eigenvalues of nonregular graphs
• Extremal Graph Realizations and Graph Laplacian Eigenvalues
• Fluctuations of extreme eigenvalues of sparse Erdős-Rényi graphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Extrema of graph eigenvalues
• Eigenvalues outside the bulk of inhomogeneous Erdős-Rényi random graphs
• On the extensional eigenvalues of graphs
• On the distribution of the maximum eigenvalues of graphs

zbMATH Keywords

eigenvalue rigiditysparse random matrixErdős-Rényi graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Spectral radii of sparse random matrices
• The eigenvalues of random symmetric matrices
• Expander graphs and their applications
• Title not available (Why is that?)
• The Largest Eigenvalue of Sparse Random Graphs
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• On the distribution of the roots of certain symmetric matrices
• Sparse random graphs: eigenvalues and eigenvectors
• Eigenvalue distributions of large Hermitian matrices; Wigner's semi- circle law and a theorem of Kac, Murdock, and Szegö
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral techniques applied to sparse random graphs
• Spectral norm of random matrices
• Title not available (Why is that?)
• Local law and Tracy-Widom limit for sparse random matrices
• The dimension-free structure of nonhomogeneous random matrices
• 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

Cited In (22)

• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Localized phase for the Erdős-Rényi graph
• Extreme eigenvalues of nonregular graphs
• Exceptional times of the critical dynamical Erdős-Rényi graph
• Delocalization transition for critical Erdős-Rényi graphs
• Spectral large deviations of sparse random matrices
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Algebraic and combinatorial expansion in random simplicial complexes
• Bernoulli random 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
• Rigidity of eigenvalues for \(\beta\) ensemble in multi-cut regime
• Eigenvalues of the non-backtracking operator detached from the bulk
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Outliers in spectrum of sparse Wigner matrices
• The completely delocalized region of the Erdős-Rényi graph
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Non-backtracking spectra of weighted inhomogeneous random graphs
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Detection thresholds in very sparse matrix completion
• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs

This page was built for publication: Extremal eigenvalues of critical Erdős-Rényi graphs

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