On the Second Eigenvalue and Random Walks in Random $d$-Regular Graphs
• Postscript version.
• Dvi version.
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 \begin{displaymath} \E{|\lambda_2(G)|^m} \le \Biggl( 2\sqrt{2d-1} \Biggl(1+\frac{\log d}{\sqrt{2d}}+O\biggl(\frac{1}{\sqrt{d}}\biggr)\Biggr) +O\biggl(\frac{d^{3/2}\log\log n}{\log n}\biggr) \Biggr)^m \end{displaymath} \begin{displaymath} \E{|\lambda_2(G)|^m} \le \Biggl( 2\sqrt{2d-1} \Biggl(1+\frac{\log d}{\sqrt{2d}}+O\biggl(\frac{1}{\sqrt{d}}\biggr)\Biggr) +O\biggl(\frac{d^{3/2}\log\log n}{\log n}\biggr) \Biggr)^m \end{displaymath} for any $m\le 2\bigl\lfloor\log n\,\lfloor\sqrt{2d-1}/2\rfloor/\log d\bigr\rfloor$, where $\E{\,}$ denotes the expected value over a certain probablity space of $2d$-regular graphs. It follows, for example, that for fixed $d$ the second eigenvalue's magnitude is no more than $2\sqrt{2d-1}+2\log d + C'$ with probability $1-n^{-C}$ for constants $C$ and $C'$ for sufficiently large $n$.