 |
On the Second Eigenvalue and Random Walks in Random $d$-Regular Graphs
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
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$.
|