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*

[...] group in terms of on . But on a small, connected graph cannot be too close to zero by the discrete Cheeger inequality. In this way, we arrive at a contradiction if the image of the action is too small. Theorem 2 [...]

Pingback by Eigenvalue multiplicity and growth of groups « tcs math - some mathematics of theoretical computer science — June 15, 2008 @ 9:25 am

[...] For the proof, I’ll refer to Theorem 4 in Alon-Klartag. Note that the proof for the Dirichlet version is even simpler than for the “standard” (Neumann) eigenvalues—it’s just a straightforward combination of Cauchy-Schwarz and the coarea formula. [...]

Pingback by Lecture 2: Spectral partitioning and near-optimal foams « tcs math - some mathematics of theoretical computer science — September 26, 2008 @ 2:12 am