A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
• Postscript version.
• Dvi version.
A $d$-regular graph has largest or first (adjacency matrix) eigenvalue $\lambda_1=d$. Consider for an even $d\ge 4$, a random $d$-regular graph model formed from $d/2$ uniform, independent permutations on $\intn$. We shall show that for any $\epsilon>0$ we have all eigenvalues aside from $\lambda_1=d$ are bounded by $2\sqrt{d-1}\;+\epsilon$ with probability $1-O(n^{-\tau})$, where $\tau=\lceil \bigl(\sqrt{d-1}\;+1\bigr)/2 \rceil-1$. We also show that this probability is at most $1-c/n^{\tau'}$, for a constant $c$ and a $\tau'$ that is either $\tau$ or $\tau+1$ (more often'' $\tau$ than $\tau+1$). We prove related theorems for other models of random graphs, including models with $d$ odd. These theorems resolve the conjecture of Alon, that says that for any $\epsilon>0$ and $d$, the second largest eigenvalue of most'' random $d$-regular graphs are at most $2\sqrt{d-1}\;+\epsilon$ (Alon did not specify precisely what most'' should mean or what model of random graph one should take).