[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.
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 .
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.