*In which we finish the proof of Cheeger’s inequalities.*

It remains to prove the following statement.

**Lemma 1** * Let be a vector with non-negative entries. Then there is a such that*

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

because

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

### Like this:

Like Loading...

*Related*

Typo: in the one before last inequality there are missing square (^2) for y_v.