Advertisements

In this lecture, we generalized our setting to weighted graphs *normalized Laplacian*, defined by

which operates on functions

In particular, we associated with

and we showed that we can express the second-smallest eigenvalue as

We defined the *expansion* of a subset

where

Finally, we defined the *expansion of a graph* by

We then stated and (almost) proved the following discrete Cheeger inequality.

Theorem 1.For any weighted graph, we have

, where

.

### Exercises (optional)

- Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.
- We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.

Advertisements