Spectrum of sparse random graphs and related problems

Abstract

We consider the normalized adjacency matrix $H$ of Erd\H{o}s-R\'{e}nyi graphs $\mathcal{G}(N,p)$ and assume $N^{\epsilon} < pN < N^{1-\epsilon}$. When $pN < N^{1/3-\epsilon}$, it was recently shown that leading order fluctuations of extreme eigenvalues of $H$ are given by a single random variable associated with the total degree of the graph (Huang-Landon-Yau, 2020

He-Knowles, 2021). We construct a sequence of random correction terms to capture higher (sub-leading) order fluctuations of extreme eigenvalues of $H$. Using these random correction terms, we prove a local law up to a (randomly) shifted edge and recover the rigidity of extreme eigenvalues under some random corrections in the sparse regime $pN > N^{\epsilon}$. In another direction, we investigate the noise sensitivity of the top eigenvector of $H$. Let $v$ be the top eigenvector of $H$. We resample $k$ uniformly randomly chosen entries of the matrix and obtain another realization of the random matrix with top eigenvector $v^{[k]}$. Building on recent results on sparse random matrices and a noise sensitivity analysis previously developed for Wigner matrices, we prove that, if $pN\geq N^{2/9}$, with high probability, when $k \ll N^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost collinear and, on the contrary, when $k\gg N^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost orthogonal.