Remarks on Lecture 1


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 .

  1. 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.
  2. 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 .]