The Cheeger-Alon-Milman inequality

[See comments on the post and the update below for the corrected argument.]

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 [the next inequality is wrong]

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

A better (and even correct) way to think about the argument [4-Nov-2015]

Define $h_G(S) = \frac{e(S,\bar S)}{|S|}$ and for ${f : V \rightarrow \mathbb R}$ define $R_G(f)=\frac{\sum_{ij \in E} (f(i)-f(j))^2}{\sum_{i \in V} f(i)^2}$ and ${\textrm{supp}(f) = \{ i \in V : f(i) \neq 0 \}}$ .

Lemma (Cheeger with boundary conditions) For any ${f : V \rightarrow \mathbb R}$ , there is a subset ${S \subseteq \textrm{supp}(f)}$ with

$\displaystyle h_G(S) \leq \sqrt{2 d_{\max} R_G(f)}\,.$

Proof: We may assume that ${\textrm{supp}(f) \neq V}$ , else taking ${S=V}$ finishes the argument. For ${t \in [0,\infty)}$ , define a subset ${S_t = \{ i \in V : f(i)^2 > t \}}$ . Observe that for every ${t \geq 0}$ , the inclusion ${S_t \subseteq \textrm{supp}(f)}$ holds by construction.

Then we have the estimate,

$\displaystyle \int_0^\infty |S_t|\,dt= \sum_{i \in V} f(i)^2$

as well as,

$\displaystyle \begin{array}{rcl} \int_0^\infty e(S_t,\overline{S_t})\,dt &=& \sum_{ij \in E} \left|f(u)^2-f(v)^2\right| \\ &= & \sum_{ij \in E} |f(i)-f(j)| \cdot |f(i)+f(j)| \\ &\leq & \sqrt{\sum_{ij \in E} (f(i)-f(j))^2} \sqrt{\sum_{ij \in E} (f(i)+f(j))^2} \\ &\leq & \sqrt{\sum_{ij \in E} (f(i)-f(j))^2} \sqrt{2 d_{\max} \sum_{i \in V} f(i)^2} \end{array}$

Combining these two inequalities yields,

$\displaystyle \frac{\int_0^\infty e(S_t,\overline{S_t})\,dt}{ \int_0^\infty |S_t|\,dt} \leq \sqrt{2 d_{\max} R_G(f)},$

implying there exists a ${t \in [0,\infty]}$ for which ${S_t}$ satisfies the statement of the lemma. $\Box$

Now to prove the Cheeger inequality, consider any map ${\phi : V \rightarrow \mathbb R}$ with ${\sum_{i \in V} \phi(i)=0}$ . Let ${m}$ be some median of the set ${\phi(V)}$ and consider the two functions ${\phi_0(i)=\max(0,\phi(i)-m)}$ and ${\phi_1(i)=\max(0,m-\phi(i))}$ . By the definition of ${m}$ , applying the lemma to either ${\phi_0}$ or ${\phi_1}$ yields a set with ${|S| \leq n/2}$ .

But we also have

$\displaystyle \sum_{i \in V} \phi_0(i)^2+\phi_1(i)^2 =\sum_{i \in V} (\phi(i)-m)^2 = nm^2 +\sum_{i \in V} \phi(i)^2 \geq \sum_{i \in V} \phi(i)^2\,,$

where we have used the fact that ${\sum_{i \in V} \phi(i)=0}$ . Thus we have at least one of ${R_G(\phi_0) \leq 2 \,R_G(\phi)}$ or ${R_G(\phi_1) \leq 2 \, R_G(\phi)}$ , completing the proof.

5 thoughts on “The Cheeger-Alon-Milman inequality”

Pingback: Eigenvalue multiplicity and growth of groups « tcs math - some mathematics of theoretical computer science
Pingback: Lecture 2: Spectral partitioning and near-optimal foams « tcs math - some mathematics of theoretical computer science
Harald Andrés Helfgott says:

November 4, 2015 at 2:12 am

I think there is an issue with the proof of the Theorem – the first inequality after “observe that” isn’t obvious – in fact it doesn’t look as if it were in general true. Doesn’t this get fixed if you define $\phi_0(x)$ to be $\max(\phi(x)-m,0)$, and similarly for $\phi_1$?
James says:

November 4, 2015 at 6:17 am

Yes, I agree. In retrospect, this was a rather poor illustration anyway, since it doesn’t emphasize the point that we are really comparing $\frac{e(S,\bar S)}{|S| |\bar S|}$ to $\frac{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}{\sum_{i,j} |\phi(i)-\phi(j)|^2}$ . The latter quantity is translation invariant, so we can choose $m=0$ (in which case your suggestion and the current incorrect definition coincide).
James says:

November 4, 2015 at 7:05 am

Thanks Harald–I appended the argument in a conceptually simpler form, breaking Cauchy-Schwartz and “localization” of the eigenfunction into separate steps.

tcs math

some mathematics & computation

The Cheeger-Alon-Milman inequality

Like this:

Related

5 thoughts on “The Cheeger-Alon-Milman inequality”

Leave a Reply Cancel reply