
A Proof of Alon's Second Eigenvalue Conjecture and Related Problems
 Postscript version.
 Dvi version.
 PDF version.

Abstract:
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{d1}\;+\epsilon$ with probability $1O(n^{\tau})$,
where $\tau=\lceil \bigl(\sqrt{d1}\;+1\bigr)/2 \rceil1$.
We also show that this probability is at most $1c/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{d1}\;+\epsilon$ (Alon did not specify precisely
what ``most'' should mean or what model of random graph one should
take).
