On the second eigenvalue and random walks in randomd-regular graphs

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ₂, of (the adjacency matrix of) a randomd-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 thek-th step, for various values ofk. Our main theorem about eigenvalues is that $$E|lambda _2 (G)|^m leqslant left( {2sqrt {2d - 1} left( {1 + frac{{log d}}{{sqrt {2d} }} + 0left( {frac{1}{{sqrt d }}} right)} right) + 0left( {frac{{d^{3/2} log log n}}{{log n}}} right)} right)^m $$ for any (m leqslant 2leftlfloor {log nleftlfloor {sqrt {2d - } 1/2} rightrfloor /log d} rightrfloor ) , where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than (2sqrt {2d - 1} + 2log d + C') with probability 1?n ^?C for constantsC andC′ for sufficiently largen.