# CS294 Lecture 4: Cheeger Inequalities cont’d

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

It remains to prove the following statement.

Lemma 1 Let ${{\bf y}\in {\mathbb R}^V_{\geq 0}}$ be a vector with non-negative entries. Then there is a ${0< t \leq \max_v \{ y_v \} }$ such that

$\displaystyle \phi ( \{ v : y_v \geq t \} ) \leq \sqrt {2 R_L({\bf y}) }$

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 ${\max_v y_v = 1}$. We consider the probabilistic process in which we pick ${t>0}$ in such a way that ${t^2}$ is uniformly distributed in ${[0,1]}$ and then define the non-empty set ${S_t := \{ v : y_v \geq t \}}$.

We claim that

$\displaystyle \frac{\mathop{\mathbb E} E(S_t, V-S_t)}{\mathop{\mathbb E} d |S_t|} \leq \sqrt{2 R_L({\bf y})} \ \ \ \ \ (1)$

Notice that Lemma 1 follows from such a claim, because of the following useful fact.

Fact 2 Let ${X}$ and ${Y}$ be random variables such that ${\mathop{\mathbb P} [ Y>0] = 1}$. Then

$\displaystyle \mathop{\mathbb P} \left[ \frac{X}{Y} \leq \frac{\mathop{\mathbb E} X}{\mathop{\mathbb E} Y} \right] > 0$

Proof: Call ${r:= \frac{\mathop{\mathbb E} X}{\mathop{\mathbb E} Y}}$. Then, using linearity of expectation, we have ${\mathop{\mathbb E} X - rY = 0}$, from which it follows ${\mathop{\mathbb P} [ X - rY \leq 0] >0}$, but, whenever ${Y>0}$, which we assumed to happen with probability 1, the conditions ${X-rY \leq 0}$ and ${\frac {X}{Y} \leq r}$ are equivalent. $\Box$

It remains to prove (1).

To bound the denominator, we see that

$\displaystyle \mathop{\mathbb E} d |S_t| = d\cdot \sum_{v\in V} \mathop{\mathbb P} [ v \in S_t] = d \sum_v y_v^2$

because

$\displaystyle \mathop{\mathbb P} [ v \in S_t] = \mathop{\mathbb P} [ y_v \geq t ] = \mathop{\mathbb P} [ y^2_v \geq t^2 ] = y^2_v$

To bound the numerator, we say that an edge is cut by ${S_t}$ if one endpoint is in ${S_t}$ and another is not. We have

$\displaystyle \mathop{\mathbb E} E(S_t,V-S_t) = \sum_{\{ u,v \} \in E} \mathop{\mathbb P} [ \{u,v\} \mbox{ is cut} ]$

$\displaystyle = \sum_{\{u,v\} \in E} | y_v^2 - y_u^2|= \sum_{\{u,v\} \in E} | y_v - y_u|\cdot (y_u + y_v)$

Applying Cauchy-Schwarz, we have

$\displaystyle \mathop{\mathbb E} E(S_t,V-S_t) \leq \sqrt{ \sum_{\{u,v\} \in E} ( y_v - y_u)^2} \cdot \sqrt{ \sum_{\{u,v\} \in E} ( y_v + y_u)^2 }$

and applying Cauchy-Schwarz again (in the form ${(a+b)^2 \leq 2a^2 + 2b^2}$) we get

$\displaystyle \sum_{\{u,v\} \in E} ( y_v + y_u)^2 \leq \sum_{\{u,v\} \in E} 2y_v + 2y_u^2 = 2d\sum_v y_v^2$

Putting everything together gives

$\displaystyle \frac{\mathop{\mathbb E} E(S_t, V-S_t)}{\mathop{\mathbb E} d |S_t|} \leq \sqrt{2 \frac { \sum_{\{u,v\} \in E} ( y_v - y_u)^2 } { d\sum_v y_v^2} }$

which is (1).

## One thought on “CS294 Lecture 4: Cheeger Inequalities cont’d”

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