Spectral radii of sparse random matrices
By Florent Benaych-Georges, Charles Bordenave, Antti Knowles. 2017
124 citations recorded by the source corpus.
We establish bounds on the spectral radii for a large class of sparse random matrices, which includes the adjacency matrices of inhomogeneous Erdős-Renyi graphs. Our error bounds are sharp for a large class of sparse random matrices. In particular, for the Erdős-Renyi graph $G(n,d/n)$, our results imply that the smallest and second-largest eigenvalues of the adjacency matrix converge to the edges of the support of the asymptotic eigenvalue distribution provided that $d \gg \log n$. Together with the companion paper [3], where we analyse the extreme eigenvalues in the complementary regime $d \ll \log n$, this establishes a crossover in the behaviour of the extreme eigenvalues around $d \sim \log n$. Our results also apply to non-Hermitian sparse random matrices, corresponding to adjacency matrices of directed graphs. The proof combines (i) a new inequality between the spectral radius of a matrix and the spectral radius of its nonbacktracking version together with (ii) a new application of the method of moments for nonbacktracking matrices.
Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability, Pure Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geometry and Topology
- Antti Knowles
- Raphael Ducatez
- J. Alt
- Florent Benaych-Georges
- Pierre Youssef
- Horng-Tzer Yau
- Jiaoyang Huang
- Ramon van Handel
In Mathematical Physics
- Antti Knowles
- Horng-Tzer Yau
- Jiaoyang Huang
- Charles Bordenave
- Jun Yin
- Florent Benaych-Georges
- Raphael Ducatez
- J. Alt
In Statistics and Probability
- Antti Knowles
- Charles Bordenave
- Horng-Tzer Yau
- Florent Benaych-Georges
- Jiaoyang Huang
- Jun Yin
- Raphael Ducatez
- J. Alt
In Pure Mathematics
- Antti Knowles
- Raphael Ducatez
- J. Alt
- Ramon van Handel
- Rafal Latala
- Pierre Youssef
- Florent Benaych-Georges
- Charles Bordenave
Citations in the corpus
- Big Bird: Transformers for Longer Sequences (2020, background): “As a consequence, such a random graph approximates the complete graph spectrally and its second eigenvalue (of the adjacency matrix) is quite far from the first eigenvalue [9, 10, 6].”
- The dimension-free structure of nonhomogeneous random matrices (2017, methodology): “This completes the proof, however, as G[2] contains the single edge {1, 2}.”
- Extremal eigenvalues of critical Erdős–Rényi graphs (2021, methodology): “By Johannes Alt and Raphaël Ducatez and Antti Knowles University of Geneva We complete the analysis of the extremal eigenvalues of the adjacency matrix A of the Erdős-Rényi graph G(N, d/N) in the critical regime d log N of the transition uncovered in [2, 3], where the regimes d log N and d log N wer”
- Largest eigenvalues of sparse inhomogeneous Erdős–Rényi graphs (2017, methodology): “Moreover, as stated above, in the companion paper [4] we prove that the Erdős-Rényi graph belongs to class (a) if d log n.”
- Transition from Tracy–Widom to Gaussian fluctuations of extremal eigenvalues of sparse Erdős–Rényi graphs (2017, background): “The sharp estimates were derived in [6,7], it was proven that the spectral norm converges to 2 if and only if p logN/N .”
- Spectral Gaps of Random Graphs and Applications (2012, unknown): “Newer methods have been pursued in [5, 6, 34].”