In which we finish the proof of Cheeger’s inequalities.
It remains to prove the following statement.
We will provide a probabilistic proof. Without loss of generality (multiplication by a scalar does not affect the Rayleigh quotient of a vector) we may assume that . We consider the probabilistic process in which we pick in such a way that is uniformly distributed in and then define the non-empty set .
We claim that
Notice that Lemma 1 follows from such a claim, because of the following useful fact.
Fact 2 Let and be random variables such that . Then
Proof: Call . Then, using linearity of expectation, we have , from which it follows , but, whenever , which we assumed to happen with probability 1, the conditions and are equivalent.
It remains to prove (1).
To bound the denominator, we see that
To bound the numerator, we say that an edge is cut by if one endpoint is in and another is not. We have
Applying Cauchy-Schwarz, we have
and applying Cauchy-Schwarz again (in the form ) we get
Putting everything together gives
which is (1).