Proof of Alon's Second Eigenvalue Conjecture and Related Problems

Proof of Alon's Second Eigenvalue Conjecture and Related Problems Synopsis

A $d$-regular graph has largest or first (adjacency matrix) eigenvalue $lambda_1=d$. Consider for an even $dge 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 $2sqrt{d-1};+epsilon$ with probability $1-O(n^{- au})$, where $ au=lceil igl(sqrt{d-1};+1igr)/2 ceil-1$. He also shows that this probability is at most $1-c/n^{ au'}$, for a constant $c$ and a $ au'$ that is either $ au$ or $ au+1$ ("e;more often"e; $ au$ than $ au+1$). He proves related theorems for other models of random graphs, including models with $d$ odd.