The second largest eigenvalue of a regular graph

Let $\Gamma$ be a regular graph of valency $k$ on $v$ vertices, and assume that (for some real constant $\lambda$) we have $\vert\theta\vert \le \lambda$ for all eigenvalues $\theta \ne k$. The ratio $\lambda / k$ determines randomness and expansion properties of $\Gamma$: the smaller $\lambda / k$, the more random, and the better expander $\Gamma$ is.

For example, the following proposition says that most points have approximately the expected number of neighbours in a given subset of the vertex set.

Proposition 1.12.1   Let $R$ be a subset of size $r$ of the vertex set $X$ of $\Gamma$. Then

$$\sum_{x \in X} ( \vert\Gamma(x) \cap R\vert - {rk \over v})^2 \le {r(v-r) \over v} \lambda^2 .$$

Proof:     Apply interlacing to $A^2$ and the partition $\{R, X \setminus R \}$ of $X$. $\Box$

An expander is a graph with the property that the number of points at distance at most one from any given (not too large) set is at least a fixed constant (larger than one) times the size of the given set. Expanders became famous because of their rôle in sorting networks (cf. Ajtai-Komlós-Szemerédi [1]) and have since found many other applications. The above proposition already implies that there cannot be too many vertices without neighbours in $R$. A better bound was given by Tanner [32] (in order to show that generalized polygons are good expanders).

Proposition 1.12.2   (Tanner [32]) Let $R$ be a set of $r$ vertices of $\Gamma$ and let $\Gamma(R)$ be the set of vertices adjacent to some point of $R$. Then

$${\vert\Gamma(R)\vert \over v } \ge { \rho \over \rho + {\lambda^2 \over k^2} (1 - \rho)}$$

where $\rho = r/v$.

Proof:     Let $\chi$ be the characteristic vector of $R$. Write it as a linear combination of a set of orthonormal eigenvectors of $A$: $\chi = \sum \alpha_i u_i$ where $Au_i = \theta_i u_i$. Then $A \chi = \sum \alpha_i \theta_i u_i$ and $(A\chi,A\chi) = \sum \alpha_i^2 \theta_i^2$, so that $\Vert A\chi \Vert^2 \le \alpha_0^2 (\theta_0^2 - \lambda^2) + \lambda^2 \sum \a... ...mbda^2) + \lambda^2 (\chi,\chi) = {r^2 \over v} (k^2 - \lambda^2) + r \lambda^2$. Now let $\psi$ be the characteristic vector of $\Gamma(R)$. Then $k^2r^2 = (A\chi,1)^2 = (A\chi,\psi)^2 \le \Vert A\chi \Vert^2 \Vert\psi \Vert^2 \le \vert\Gamma(R)\vert . ({r^2 \over v} (k^2 - \lambda^2) + r \lambda^2)$, proving our claim. $\Box$