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

,

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.

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

Define and for define and .

Lemma (Cheeger with boundary conditions)For any , there is a subset with

*Proof:* We may assume that , else taking finishes the argument. For , define a subset . Observe that for every , the inclusion holds by construction.

Then we have the estimate,

as well as,

Combining these two inequalities yields,

implying there exists a for which satisfies the statement of the lemma.

Now to prove the Cheeger inequality, consider any map with . Let be some median of the set and consider the two functions and . By the definition of , applying the lemma to either or yields a set with .

But we also have

where we have used the fact that . Thus we have at least one of or , completing the proof.

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

Yes, I agree. In retrospect, this was a rather poor illustration anyway, since it doesn’t emphasize the point that we are really comparing to . The latter quantity is translation invariant, so we can choose (in which case your suggestion and the current incorrect definition coincide).

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