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.