The Cheeger-Alon-Milman inequality

Recently, Luca posted on Cheeger’s inequality. Whenever I try to reconstruct the proof, I start with the coarea formula and then play around with Cauchy-Schwarz (essentially the way that Cheeger proved it). The proof below turned out to be a bit more complicated than I thought. Oh well…

Let $G = (V,E)$ be a graph with maximum degree $d_{\max}$ and $n = |V|$. Let’s work directly with the sparsity $\displaystyle \alpha_G = \min_{S \subseteq V} \frac{e(S,\bar S)}{|S| |\bar S|}$ which is a bit nicer. Notice that $\alpha_G n$ is within factor 2 of the Cheeger constant $h_G$. We start with a very natural lemma:

Coarea lemma: For any $f : V \to \mathbb R$, we have $\sum_{ij \in E} |f(i)-f(j)| \geq \alpha_G \sum_{i,j \in V} |f(i)-f(j)|$.

Proof: Let $V_r = \{ i : f(i) \leq r \}$, then we can write $\sum_{ij \in E} |f(i)-f(j)|$ as the integral

$\displaystyle \int_{-\infty}^{\infty} e(V_r, \bar V_r) dr \geq \alpha_G \int_{-\infty}^{\infty} |V_r| |\bar V_r|dr = \alpha_G \sum_{i,j \in V} |f(i)-f(j)|$

Now a bit of spectral graph theory: $L = D - A$ is the Laplacian of $G$, where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix. The first eigenvalue is $\lambda_1 = 0$ and the first eigenvector is $(1,1,\ldots,1)$. If $\phi : V \to \mathbb R$ is the second eigenvector, then the second eigenvalue can be written

$\displaystyle \lambda_2 = \frac{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}{\sum_{i \in V} \phi(i)^2} \quad(1)$

Given (1), it is natural to apply the coarea formula with $f(i) = \phi(i)^2$ and then play around.

Theorem: $\displaystyle \lambda_2 \geq \frac{\alpha_G^2 n^2}{32 d_{\max}}$

Proof: Unfortunately, if we try $f(i) = \phi(i)^2$, it doesn’t quite work (think of the case when $\phi$ takes some value $v$ and $-v$ equally often). Instead, let’s eliminate this case by setting $\phi_0(i) = \max(m,\phi(i))$, where $m = \mathrm{med}(\phi)$. Now applying the coarea lemma with $f(i) = \phi_0(i)^2$ yields:

$\displaystyle \alpha_G \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| \leq \sum_{ij \in E} |\phi_0(i)^2-\phi_0(j)^2|$

$\displaystyle = \sum_{ij \in E} |\phi_0(i)+\phi_0(j)||\phi_0(i)-\phi_0(j)| \leq \sqrt{\sum_{ij \in E} [\phi_0(i)+\phi_0(j)]^2} \sqrt{\sum_{ij \in E} |\phi_0(i)-\phi_0(j)|^2}$

$\displaystyle \leq \sqrt{2 d_{\max}} \sqrt{n m^2 + \sum_{i \in V} \phi(i)^2} \sqrt{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}\quad\quad (2)$

Notice that the same inequality holds for $\phi_1(i) = \min(m, \phi(i))$. Also, observe that

$\displaystyle \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| + |\phi_1(i)^2-\phi_1(j)^2|$

$\displaystyle \geq \frac{n}{2} \sum_{i : \phi(i) \geq m} [\phi(i)-m]^2 + \frac{n}{2} \sum_{i : \phi(i) \leq m} [\phi(i)-m]^2$

$\displaystyle = \frac{n}{2} \sum_{i \in V} [\phi(i)-m]^2 = \frac{n}{2} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right]$,

where in the final line we have used the fact that $\sum_{i \in V} \phi(i) = 0$ since $\phi$ is orthogonal to the first eigenvector.

So we can assume that $\displaystyle \sum_{i,j \in V} |\phi_0(i)-\phi_0(j)|^2 \geq \frac{n}{4} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right]$. Plugging this into (2), rearranging, and using (1) yields the claim.