Upper Tails for Edge Eigenvalues of Random Graphs

Bhaswar B. Bhattacharya, Shirshendu Ganguly

Published 2018-11-19, updated 2020-11-28Version 2

The upper tail problem for the largest eigenvalue of the Erd\H{o}s--R\'enyi random graph $\mathcal{G}_{n,p}$ is to estimate the probability that the largest eigenvalue of the adjacency matrix of $\mathcal{G}_{n,p}$ exceeds its typical value by a factor of $1+\delta$. In this note we show that for $\delta >0$ fixed, and $p \rightarrow 0$ such that $n^{\frac{1}{2}} p \rightarrow \infty$, the upper tail probability for the largest eigenvalue of $\mathcal{G}_{n,p}$ is $$\exp\left[-(1+o(1)) \min\left\{\tfrac{(1+\delta)^2}{2}, \delta(1+\delta) \right\} n^{2}p^{2}\log (1/p)\right].$$ In the same regime of $p$, we show that the second largest eigenvalue $\lambda_2( \mathcal G_{n,p})$ of the adjacency matrix of $\mathcal{G}_{n,p}$ satisfies $$\mathbb P(\lambda_2(\mathcal G_{n,p})\ge \delta np) = \exp\left[-(1+o(1)) \tfrac{1}{2} \delta^2n^2p^2 \log (1/p) \right],$$ where $\delta =\delta_n < 1$ can depend on $n$ such that $\delta n^{\frac{1}{2}} p \rightarrow \infty$, which covers deviations of $\lambda_2(\mathcal G_{n,p})$ between $n^{\frac{1}{2}}$ and $np$. Our arguments build on recent results on the large deviations of the largest eigenvalue and related non-linear functions of the adjacency matrix in terms of natural mean-field entropic variational problems.