A Proof of Alon's Second Eigenvalue Conjecture

Joel Friedman, University of British Columbia

Noga Alon conjectured in the mid 1980's that for fixed integer d > 2 and for any fixed epsilon > 0 we have that for large n, "most d-regular graphs on n verices" have second largest (adjacency matrix) eigenvalue bounded above by 2 * sqrt(d-1) + epsilon. We shall explain some applications of this conjecture (especially to expanders) and give some indication of its proof. We shall describe possible generalizations.