ON THE 2ND EIGENVALUE AND RANDOM-WALKS IN RANDOM D-REGULAR GRAPHS

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, lambda-2, of (the adjacency matrix of) a random d-regular graph, G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at the k-th step, for various values of k. Our main theorem about eigenvalues is that [GRAPHICS] for any m less-than-or-equal-to 2 left-perpendicular log n left-perpendicular square-root 2d-1/2 right-perpendicular / log d right-perpendicular, where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixed d the second eigenvalue's magnitude is no more than 2 square-root 2d-1 + 2 log d + C' with probability 1 - n-C for constants C and C' for sufficiently large n.