This homework is due in two weeks on Wednesday, April 18th. You make work in small groups of 2 or 3. You should reference any discussions with others, books, lecture notes, or other resources that you use in coming up with a solution.

[**Reminder:** The notation is the same as and is defined as the conjuniction of and .]

### Problems

- Let be the adjacency matrix of a -regular graph . Prove that is bipartite if and only if has as an eigenvalue.
- Consider the two-dimensional grid graph . Let . Prove that
where refers to the second eigenvalue of the combinatorial Laplacian. (Prove this without using the Spielman-Teng theorem for planar graphs.) For the lower bound, it may help to remember that , where is the path on vertices.

- Let for some integer . Prove that if is the complete binary tree of height , we have
where again refers to the combinatorial Laplacian.

- Let be an arbitrary graph. Recall that
Let be the second eigenvalue of the combinatorial Laplacian on .

Prove that,

and

where both minimums are over non-constant functions.

- Let be a -regular graph and set , where is the adjacency matrix of . Let be defined as in the notes for lecture 3. Let be the eigenvalues of . Prove that
by evaluating in two different ways.

Doesn’t the second eigenvalue of the path on n vertices goes as 1/n^2?

Yes. I fixed this in the problem.

For problem 4, I assume the minimum is over functions orthogonal to the constant function. Is this the minimum for as well?

You’re right, there is a bug..

The optimizations should be . I fixed the problem.

But you do not need to make any other assumptions about f.

In Problem 4, min should be taken over nonconstant functions? Otherwise we can just get it to 0.

Sure, you can assume it’s over non-constant functions. If the function is constant, then the maximum is undefined (0/0).

Could you say a little about the significance of the results in problems 4 and 5? It seems like there is more going on here than meets the eye, but I don’t quite see it.