In this lecture, we generalized our setting to weighted graphs where is a positive weight function on edges. We also looked at the basic spectral theory of the *normalized Laplacian*, defined by

,

which operates on functions via

.

In particular, we associated with the normalized Rayleigh quotient,

,

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

.

We defined the *expansion* of a subset by

,

where is the characteristic function for .

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

Is (2) still true if we allow arbitrary edge weights? It seems like both lambda_2 and the edge expansion scale proportionately…. but I couldn’t figure out the asymptotic bound.

Both the Rayleigh quotient and the expansion (which is just the Rayleigh quotient of a characteristic function) are homogeneous in the weights. So if you scale the weights uniformly, the bound will remain true. If you put arbitrary weights on the edges, you can get any Laplacian you want essentially, so then no, it doesn’t hold.

A small typo: the right hand side of the Cheeger inequality should be sqrt(2\lambda) instead of 2 sqrt(2lambda).

A small typo: the right-hand side of Cheeger’s inequality should be \sqrt{2\lambda} instead of 2\sqrt{\lambda}

Both bounds are true. I only proved the slightly weaker one in class.