A particular argument in the review on expanders by Hoory-Linial-Wigderson

Question

I am thinking about the third bullet point on page 455 here, http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/

• Can someone explain what is the argument there which seems to conclude that for arbitrary $d-$regular graphs on $n$ vertices with their second highest adjacency eigenvalue $\lambda_2(A) \leq \alpha d$ it should follow that $d = O(log (n))$. How!? (Isn't some such a thing true only for Abelian Cayley graphs?)

---

The only part of that thrid bullet point is that I can understand is its last-but-two line - as to how it follows from the ``Expander Mixing Lemma" that for all $S \subseteq V$ we have $\frac{E(S,S)}{\vert S \vert } \leq d(\alpha + \frac{\vert S \vert }{n})$. This just comes from setting the two sets equal to $S$ in the EML.

• But how is the above the same as $\frac{E(S,\bar{S})}{\vert S \vert } \geq d((1-\alpha) - \frac{\vert S \vert }{n})$ ?

• But $S$ has at least $\frac{E(S,\bar{S}) }{d}$ neighbours? Why? Isn't every edge in $E(S,\bar{S})$ corresponding to a neighbour of $S$ by definition?

• From the above how does it follow that $\vert B(x,r+1)\vert \geq (1+\epsilon)\vert B(x,r)\vert$ where $\vert B(x,r) \vert \leq \frac{n}{2}$ and $\epsilon = \frac{1}{2} - \alpha$? (where $\vert B(x,r) \vert$ is the size of the set of elements who are at a distance of $r$ from $x$)

• From the above it apparently follows that $\vert B(x,r)\vert >\frac{n}{2}$ for every $x$ and some $r \leq O(log (n))$?

And how is the last statement above the same as saying that the graph has diameter $O(log(n))$?

Answer 1

• Since the graph is $d$-regular, the number of directed edges that start at a point in $S$ is exactly $d |S|$. The number with both endpoints in $S$ is $E(S,S)$. Subtracting an upper bound on this number from $d |S|$ yields the given lower bound on $E(S, \overline{S})$.

• Yes, every edge in $E(S, \overline{S})$ is a neighbor of $S$. However, since the graph is $d$-regular, there could be $d$ edges in $E(S, \overline{S})$ that all go to the same neighbor of $S$.

• The number of neighbors of $S$ that are not in $S$ is at least $E(S, \overline{S})/d$, which we know is at least $|S| \bigl((1 - \alpha) - |S|/n \bigr)$. If we assume $|S| \le n/2$ (i.e., $|S|/n \le 1/2$), this is at least $|S| \bigl( (1/2) - \alpha \bigr) = \epsilon |S|$. Now, let $S = B(x,r)$.

• Note that $B(x,r)$ is the set of vertices whose distance is $\le r$ from $x$. We have $|B(x,0)| = 1$. Then, by induction, we have $|B(x,k)| \ge (1 + \epsilon)^k$, if $|B(x,k)| \le n/2$. So the number of vertices in $B(x,k)$ grows exponentially. More specifically, taking $r = 1 + \log_{1 + \epsilon}(n/2)$, we see that $|B(x,r)| > n/2$.

• For any two vertices $x$ and $y$, we know that $|B(x,r)| > n/2$ and $|B(y,r)| > n/2$. Since there are only $n$ vertices in the entire graph, these two sets cannot be disjoint. So there is some $z$, such that there is a path of length $\le n/2$ from $x$ to $z$, and also a path of length $\le n/2$ from $z$ to $y$. Putting these two paths together yields a path of length $\le n$ from $x$ to $y$.