8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ Thanks, this is most of what I was looking for. Is there any intuition for the constant $2$ in front though? $\endgroup$ – Xiaoyu He Mar 15 '17 at 2:41
  • 2
    $\begingroup$ @XiaoyuHe Extend the argument slightly: suppose your graph has not short cycles, in particular, no 4-cycles. Then, the only paths of length 4 returning to the base point $a$ are $a-b-c-b-a$ and $a-b-a-c-a.$ There are roughly $2k^2$, so the sum of the fourth powers of the eigenvalues is $ 2 k^2 n.$ I think this already gives you the $2.$ $\endgroup$ – Igor Rivin Mar 15 '17 at 4:26
  • 2
    $\begingroup$ That gives you $2^{1/4} \sqrt{k} \approx 1.19 \sqrt{k}$. There are roughly $5 k^3$ walks of length $6$ (assuming no $4$ or $6$ cycles), giving $5^{1/6} \sqrt{k} \approx 1.30 \sqrt{k}$. To see the $\sqrt{2}$ you need to look at walks of length $2r$ and send $r \to \infty$. $\endgroup$ – David E Speyer Mar 15 '17 at 12:13
  • $\begingroup$ @DavidSpeyer Yes, you are absolutely correct - that was a midnight thought which was not quite thought out. $\endgroup$ – Igor Rivin Mar 15 '17 at 15:34
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.