The third and final homework, due June 6th.

# Category Archives: Homework

# Homework #2

This homework is due on Monday, May 14th.

# Homework #1

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.