Intuition question about the spectral definition of expander graphs

Question

Disclaimer: I don't know too much about graph theory, and next to nothing about spectral theory. I know this will probably make answering this question difficult, so I am sorry in advance!

Hi! I am reading a paper about isogeny graphs, and the paper talks about expander graphs. I am familiar with the "intuitive" definition of an expander graph: an expander graph is regular, sparse, and well-connected. The paper also gives a more "technical" definition ($\lambda_{1} \geq \lambda_{2} \geq ... \geq \lambda_{n}$ are the eignevalues of the adjacency matrix of $G$):

Let $G$ be a $d$-regular graph of degree at least 1. Let $\epsilon > 0$. Then $G$ is called a one-sided $\epsilon$-expander if \begin{equation*} \lambda_{2} \leq (1-\epsilon)k. \end{equation*} It is a two-sided $\epsilon$-expander if $G$ also satisfies \begin{equation*} \lambda_{n} \geq -(1-\epsilon)k \end{equation*}

I know that this definition loosely means that the non-trivial eignevalues of an expander graph are not too far from zero. My question is what does the eignevalues not being far from zero have to do with the graph being sparse and well-connected? I'm having trouble intuitively connecting the ideas in my head. Any help would be appreciated. Thanks so much!

Answer 1

In a $d$-regular graph, the all-ones vector is an eigenvector with eigenvalue $d$; this is $\lambda_1$, the largest eigenvalue.

If the graph is not connected at all, then the eigenspace of $d$ is multidimensional: any vector which is constant on connected components of the graph is also an eigenvector.

Now suppose $G$ is connected, but very sparsely: for some $S \subset V(G)$, there are very few edges between $S$ and $V(G)-S$. Then the vector which is $1$ on $S$ and $0$ outside $S$ is "nearly an eigenvector with eigenvalue $d$", and so there must also be an "eigenvector with eigenvalue nearly $d$" and so $\lambda_2$ is close to $d$.

We can make this rigorous with Rayleigh quotients. If $A$ is a symmetric matrix, then

• Maximizing $\frac{\mathbf x^{\mathsf T}A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$ over all $\mathbf x \ne \mathbf 0$ gives the largest eigenvalue, and the $\mathbf x$ that does it is the largest eigenvector.
• If we now maximize $\frac{\mathbf x^{\mathsf T}A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$ over all $\mathbf x \ne \mathbf 0$ perpendicular to that largest eigenvector, we get the second-largest eigenvalue, and so on.

In this case, suppose $|V(G)|=n$, $|S|=k$, and there are $t$ edges between $S$ and $V(G) -S$. Let $x_v = \frac1k$ for $v \in S$ and $x_v = -\frac1{n-k}$ for $v \notin S$. Then $\mathbf x^{\mathsf T}A\mathbf x = \frac1{k^2}(kd - t) + \frac1{(n-k)^2}((n-k)d - t) - \frac1{k(n-k)}(2t)$ and $\mathbf x^{\mathsf T}\mathbf x = k \cdot \frac1{k^2} + (n-k) \cdot \frac1{(n-k)^2}$. After some algebra, $\frac{\mathbf x^{\mathsf T}A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$ simplifies to $d - \frac{nt}{k(n-k)}$.

In particular, $\lambda_2 \ge d - \frac{nt}{k(n-k)}$ in this case. So if we are given that $\lambda_2$ is far from $d$, we conclude that $t$ cannot be too small for reasonably large $k$.