Quantitative Tracy-Widom laws for sparse random matrices

Abstract

We consider the fluctuations of the largest eigenvalue of sparse random matrices, the class of random matrices that includes the normalized adjacency matrices of the Erdős-Rényi graph $G(N,p)$. We show that the fluctuations of the largest eigenvalue converge to the Tracy-Widom law at a rate almost $O(N^{-1/3}+p^{-2}{N}^{-4/3})$ in the regime $p\gg N^{-2/3}$. Our proof builds upon the Green function comparison method initiated by Erdős, Yau, and Yin [22]. To show a Green function comparison theorem for fine spectral scales, we implement algorithms for symbolic computations involving averaged products of Green function entries.

48 pages