  In this paper we consider the problem of estimating the joint upper and lower
tail large deviations of the edge eigenvalues of an Erd\H{o}s-R\'enyi random
graph $\mathcal{G}_{n,p}$, in the regime of $p$ where the edge of the spectrum
is no longer governed by global observables, such as the number of edges, but
rather by localized statistics, such as high degree vertices. Going beyond the
recent developments in mean-field approximations of related problems, this
paper provides a comprehensive treatment of the large deviations of the
spectral edge in this entire regime, which notably includes the well studied
case of constant average degree. In particular, for $r \geq 1$ fixed, we pin
down the asymptotic probability that the top $r$ eigenvalues are jointly
greater/less than their typical values by multiplicative factors bigger/smaller
than $1$, in the regime mentioned above. The proof for the upper tail relies on
a novel structure theorem, obtained by building on estimates of Krivelevich and
Sudakov (2003), followed by an iterative cycle removal process, which shows,
conditional on the upper tail large deviation event, with high probability the
graph admits a decomposition in to a disjoint union of stars and a spectrally
negligible part. On the other hand, the key ingredient in the proof of the
lower tail is a Ramsey-type result which shows that if the $K$-th largest
degree of a graph is not atypically small (for some large $K$ depending on
$r$), then either the top eigenvalue or the $r$-th largest eigenvalue is larger
than that allowed by the lower tail event on the top $r$ eigenvalues, thus
forcing a contradiction. The above arguments reduce the problems to developing
a large deviation theory for the extremal degrees which could be of independent
interest.
