Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?

Question

Ramanujan graphs are the best spectral expanders: $\lambda_2 \le 2\sqrt{d-1}$. I'm looking for some intuition for this value $2\sqrt{d-1}$.

Friedman showed that every random $d$-regular graph achieves $\lambda_2 = 2\sqrt{d-1}+\epsilon$ and Alon-Boppana shows that every sufficiently large $d$-regular graph must have $\lambda_2 \ge 2\sqrt{d-1} - o(1)$. Unfortunately both these results seem quite involved. Is there an easy way to see that the answer should be around $2\sqrt{d-1}$, or at very least $\Theta(\sqrt{d})$? Intuition for either direction would be appreciated.

Answer 1

Yes, see this paper by Ram Murty. The basic point is that the sum of squares of the eigenvalues is the trace of the square of the adjacency matrix, which is equal to $d n.$

Answer 2

If you take an infinite regular tree of degree $d$ and fix one vertex $v$, then the number of closed walks of length $2k$ (there are none of odd length) starting at $v$ grows like $4^k(d-1)^k$ as $k\to\infty$. To see this heuristically, note that you have to move towards $v$ half the time and away from $v$ half the time. There are $2^{2k}$ choices for which steps you move away from $v$ and for each such step there are $d-1$ choices for which branch to take. As David says, this is related to the question because Ramanujan graphs are locally tree-like.

Answer 3

Heuristically, an expander $G$ looks locally like the $d$-regular tree $T$. Let $r$ be a positive real number and let $f_x$ be the function on the vertices of $T$ given by $f_x(y) = r^{d(x,y)}$. We have $|f_x|^2 = 1+d \sum_{n=1}^{\infty} (d-1)^n r^{2n}$; this sum is convergent as long as $r < 1/\sqrt{d-1}$. Writing $A$ for the adjacency matrix, we have $$A f_x = (r^{-1}+(d-1) r) f_x + (r-r^{-1}) \delta_x$$ where $\delta_x$ is the $\delta$ function at $x$. As $r \to \tfrac{1^{-}}{\sqrt{d-1}}$, the norm of $f_x$ grows while $(r-r^{-1}) \delta_x$ remains bounded. So, intuitively, at $r=1/\sqrt{d-1}$, the function $f$ acts like an eigenvector with eigenvalue $\sqrt{d-1} + (d-1)/\sqrt{d-1} = 2 \sqrt{d-1}$.

In an expander, $G$ still locally looks like $T$. Take two vertices $x$ and $y$ that are very far apart and consider $f_x - f_y$. This is orthogonal to $1$, so $\tfrac{\langle f_x-f_y, \ A (f_x - f_y) \rangle}{\langle f_x-f_y, \ f_x-f_y \rangle}$ is a lower bound for $\lambda_2$. Assuming we take $r < 1/\sqrt{d-1}$, the overlap between $f_x$ and $f_y$ will be negligible and the analysis will be dominated by the behavior near $x$ and $y$, which will look like the case of $T$.

For a rigorous proof of Alon-Boppana along vaguely these lines, see Theorem 5 here. I'm not claiming the arguments are very close, but they start with two points that are far apart and use them to build a function $g$ with $\langle g,\ 1 \rangle=0$ and $\tfrac{\langle g, A^{2k} g \rangle}{\langle g,g \rangle}$ large by using that $G$ locally looks like $T$.