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 {\displaystyle h_G(S) = \frac{e(S,\bar S)}{|S|}} and for {f : V \rightarrow \mathbb R} define {\displaystyle  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

  1. 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$?

  2. 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).

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s