Upper tail of the spectral radius of sparse Erdős-Rényi graphs

Abstract

We consider an Erdős-Rényi graph $\mathbb{G}(n,p)$ on $n$ vertices with edge probability $p$ such that \[ \sqrt{\frac{\log n}{\log \log n}} \ll np \le n^{1/2-o(1)}, \label{eq:abs} \tag{$†$} \] and derive the upper tail large deviations of $\lambda (\mathbb{G}(n,p))$, the largest eigenvalue of its adjacency matrix. Within this regime we show that, for $p\gg n^{-2/3}$ the $\log$-probability of the upper tail event of $\lambda (\mathbb{G}(n,p))$ equals to that of planting a clique of an appropriate size (upon ignoring smaller order terms), while for $p\ll n^{-2/3}$ the same is given by that of the existence of a high degree vertex. This, in particular, shows an emergence of {\em non-planted localized structure} in the latter regime. We also confirm that in the entire regime \eqref{eq:abs} the large deviation probability is asymptotically approximated by the solution of the mean-field variational problem, and further identify the typical structure of $\mathbb{G}(n,p)$ conditioned on the upper tail event of $\lambda (\mathbb{G}(n,p))$ in a certain sub-regime of $p$. For $p$ such that $\log (np)\gtrsim \log n$ the large deviations of $\lambda (\mathbb{G}(n,p))$ is deduced from those of $\mathrm{Hom}(C_{2t},\mathbb{G}(n,p))$, the homomorphism counts of cycle of length $2t$, for $t\ge 3$ and $p$ such that $n^{1/2-o(1)}\ge np\gg n^{1/t}$. In this latter regime the typical structure of $\mathbb{G}(n,p)$ conditioned on the upper tail of $\mathrm{Hom}(C_{2t},\mathbb{G}(n,p))$ is identified and asymptotic tightness of the mean-field approximation is also established.

arXiv commentMinor changes in presentation