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

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