 |
Some Graphs with Small Second Eigenvalue
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
For a $d$-regular graph, $G$,
the second largest eigenvalue in absolute value, $\lambda_2(G)$,
of $G$'s adjacency matrix gives important information about $G$.
The goal of this paper is to estimate $|\lambda_2(G)|$
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$.
We use this to show that the expected value of $|\lambda_2(G)|^m$
is no more than the $m$-th power of roughly
$2\sqrt{2d-1}+O(\log d)$,
for
integers $m\le$ roughly $\log n\,\sqrt{2d}/\log d$,
where the expected value
is taken over a certain probablity space of $d$-regular
graphs with $d$ even.
It follows that the
probability that a graph has its second eigenvalue of magnitude greater
than $(1+\epsilon)\bigl(\sqrt{2d-1}+O(\log d)\bigr)$
for any fixed $\epsilon>0$ is roughly
less than
$n^{-c\sqrt{d}/\log d}$ for a constant $c$ depending only on $\epsilon$.
As an application, it follows that ``most'' graphs can be quickly varified
to expand and magnify almost as much as is guarenteed by the best explicit
constructions currently known.
|