Today we started studying the spectrum of the combinatorial Laplacian on a graph

We saw that

I encourage you to look at the first four lectures of Spielman’s course for a refresher.

### Exercises

The best way to learn a subject is to get your hands dirty. Here are some optional exercises to help build your intuition.

Recall that for a function *Rayleigh quotient* by

If

- Prove that
by showing that (a) there exists a map with and and (b) for any such map with , we have . We did this in class, but it will help to reconstruct the proof on your own. - Try to prove that
by exhibiting an explicit subspace of test functions

that achieves this bound. It may help to use the Courant-Fischer min-max principle

which says thatwhere the minimum is over all k-dimensional subspaces

.

[Hint: Have your subspace be the span of k functions with disjoint supports, where the support of a functionis .]