The third and final homework, due June 6th.
This homework is due on Monday, May 14th.
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 .]
- 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 .
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.