A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems

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 $\\{1,\\ldots,n\\}$. The author shows that for any $\\epsilon>0$ 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$. He also shows 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$). He proves related theorems for other models of random graphs, including models with $d$ odd.