Largest eigenvalues of sparse inhomogeneous Erdős–Rényi graphs

By Florent Benaych-Georges, Charles Bordenave, Antti Knowles. 2017

91 citations recorded by the source corpus.

We consider inhomogeneous Erd\H{o}s-R\'enyi graphs. We suppose that the maximal mean degree $d$ satisfies $d \ll \log n$. We characterize the asymptotic behavior of the $n^{1 - o(1)}$ largest eigenvalues of the adjacency matrix and its centred version. We prove that these extreme eigenvalues are governed at first order by the largest degrees and, for the adjacency matrix, by the nonzero eigenvalues of the expectation matrix. Our results show that the extreme eigenvalues exhibit a novel behaviour which in particular rules out their convergence to a nondegenerate point process. Together with the companion paper [3], where we analyse the extreme eigenvalues in the complementary regime $d \gg \log n$, this establishes a crossover in the behaviour of the extreme eigenvalues around $d \sim \log n$. Our proof relies on a new tail estimate for the Poisson approximation of an inhomogeneous sum of independent Bernoulli random variables, as well as on an estimate on the operator norm of a pruned graph due to Le, Levina, and Vershynin.

Subfields: Mathematical Physics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistics and Probability

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 ﬁrst eigenvalue [9, 10, 6].”
Extremal eigenvalues of critical Erd\H{o}s-R\'enyi graphs (2019, methodology): “We complete the analysis of the extremal eigenvalues of the the adjacency matrix A of the Erdős-Rényi graph G(N, d/N) in the critical regime d logN of the transition uncovered in [2,3], where the regimes d logN and d logN were studied.”
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].”