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