|
Abstract : |
A d-regular graph has largest or first (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 {1,...,n}. We shall show that for any > 0 we have all eigenvalues aside from 1 = d are bounded by 2 ? d ? 1 + with probability 1 ? O(n?), where = ? ? ? d ? 1 + 1 ? /2 ? ? 1. We also show that this probability is at most 1 ? c/n ?, for a constant c and a ? that is either or + 1 (?more 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 > 0 and d, the second largest eigenvalue of ?most ? random dregular graphs are at most 2 ? d ? 1 + (Alon did not specify precisely what ?most ? should mean or what model of random graph one should take). 1, |
