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 be a graph with maximum degree and . Let’s work directly with the sparsity which is a bit nicer. Notice that is within factor 2 of the Cheeger constant . We start with a very natural lemma:

**Coarea lemma: **For any , we have .

**Proof: **Let , then we can write as the integral

Now a bit of spectral graph theory: is the Laplacian of , where is the diagonal degree matrix and is the adjacency matrix. The first eigenvalue is and the first eigenvector is . If is the second eigenvector, then the second eigenvalue can be written

Given (1), it is natural to apply the coarea formula with and then play around.

**Theorem: **

**Proof:** Unfortunately, if we try , it doesn’t quite work (think of the case when takes some value and equally often). Instead, let’s eliminate this case by setting , where . Now applying the coarea lemma with yields:

Notice that the same inequality holds for . Also, observe that

,

where in the final line we have used the fact that since is orthogonal to the first eigenvector.

So we can assume that . Plugging this into (2), rearranging, and using (1) yields the claim.

### Like this:

Like Loading...

*Related*

## 2 thoughts on “The Cheeger-Alon-Milman inequality”