Today we started studying the spectrum of the combinatorial Laplacian on a graph . This is the operator given by
We saw that has a spectrum of the form , and that the number of connected components in is precisely the multiplicity of .
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 , we define its Rayleigh quotient by
If is the path graph on n vertices, then as we argued today, we have .
- 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 is .]