Extremal eigenvalues of critical Erd\H{o}s-R\'enyi graphs

By J. Alt, Raphael Ducatez, Antti Knowles. 2019

8 citations recorded by the source corpus.

We complete the analysis of the extremal eigenvalues of the the adjacency matrix $A$ of the Erdős-Renyi graph $G(N,d/N)$ in the critical regime $d \asymp \log N$ of the transition uncovered in [arXiv:1704.02953,arXiv:1704.02945], where the regimes $d \gg \log N$ and $d \ll \log N$ 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 / \sqrt{d}$ 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_* = \frac{1}{\log 4 - 1} \log N$. For $d d_*$ 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$ with a Wigner matrix, in which case the role of the degrees is replaced by the squares of the $\ell^2$-norms of the rows.

Subfields: Geometry and Topology, Mathematical Physics, Statistics and Probability, Network Science & Complex Systems

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

  1. J. Ainslie

In Mathematical Physics

  1. Manzil Zaheer
  2. Kumar Avinava Dubey

In Statistics and Probability

  1. Amr Ahmed
  2. Manzil Zaheer
  3. Kumar Avinava Dubey

Citations in the corpus