A proof of alon's second eigenvalue conjecture

Abstract

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 - ε.