Finite size correction to the spectrum of regular random graphs: an analytical solution

Abstract

We develop a thorough analytical study of the $O(1/N)$ correction to the spectrum of regular random graphs with $N \rightarrow \infty$ nodes. The finite size fluctuations of the resolvent are given in terms of a weighted series over the contributions coming from loops of all possible lengths, from which we obtain the isolated eigenvalue as well as an analytical expression for the $O(1/N)$ correction to the continuous part of the spectrum. The comparison between this analytical formula and direct diagonalization results exhibits an excellent agreement, confirming the correctness of our expression.

Extended version with an extra appendix explaining the connection with rigorous results