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.
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
- 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 that
where 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 function