
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{2d1}+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{2d1}+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.
