Upper Tails for Edge Eigenvalues of Random Graphs

Abstract

The upper tail problem for the largest eigenvalue of the Erdős--Rényi 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\to 0$ such that $n^{\frac{1}{2}}p\to \infty$, the upper tail probability for the largest eigenvalue of ${\mathcal{G}}_{n,p}$ is $$\exp \left[-(1+o(1))\min \left\{\frac{(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))\frac{1}{2}{\delta }^2{n}^2{p}^2\log (1/p)\right],$$ where $\delta ={\delta }_n<1$ can depend on $n$ such that $\delta n^{\frac{1}{2}}p\to \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.

15 pages