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.

### 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 , 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 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 function is .]

For (1), is there a high level way to see the lower bound for R(f)? I follow the proof given in class but somehow it’s a hard proof to remember because it seems very arithmetic.

Specifically, why would you think to sum over choices for a fixed vertex, and why does it make sense to employ cauchy-schwarz?

Let’s normalize so that satisfies . We also know that .

These two facts together suggests that f has to have a large variance in values. For instance, it is possible to prove from these facts that . Instead of using this sum over pairs, you can just fix a vertex. This is what we did in class, and it captures the same effect.

Now you want to say that any function which varies a lot (in this sense) must have to vary somewhat along edges. Consider the endpoints of the path and . We know that the edges in between much “pay” for the stretch . The cheapest way to do this (because we’re looking at a sum of squares) is for every edge to be of length . Cauchy-Schwarz is the formal way to prove that this is “cheapest.”