A proof of Alon’s second eigenvalue conjecture and related problems

Ad-regular graph has largest or rst (adjacency matrix) eigenvalue 1 = d. Consider for an even d 4, a random d-regular graph model formed from d=2 uniform, independent permutations on f1;: : : ;ng. We shall show that for any >0 we have all eigenvalues aside from 1 = d are bounded by 2 p d 1+ with probability 1 O (n), where =d p d 1+ 1 =2e 1. We also show that this probability is at most 1 c=n 0, for a constant c and a 0 that is either or +1 (often than + 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 > 0a ndd, the second largest eigenvalue of random dregular graphs are at most 2 p d 1+ (Alon did not specify precisely what should mean or what model of random graph one should take).