a proof of alon's second eigenvalue conjecture
A d-regular graph has largest or first (adjacency matrix) eigenvalue ? 1 = d. In this paper we show the following conjecture of Alon. Fix an integer d > 2 and a real ? > 0. Then for sufficiently large n we have that "most" d-regular graphs on n vertices have all their eigenvalues except ? 1 = d bounded above by 2?d-1 + ?. Our methods, being trace methods, also bound those eigenvalues below by -2?d-1 - ?.
eigenvalues expanders random graphs