# Homework #3

The third and final homework, due June 6th.

Advertisements

# 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 ${A \lesssim B}$ is the same as ${A \leq O(B)}$ and ${A \asymp B}$ is defined as the conjuniction of ${A \lesssim B}$ and ${B \lesssim A}$.]

### Problems

1. Let ${A}$ be the adjacency matrix of a ${d}$-regular graph ${G}$. Prove that ${G}$ is bipartite if and only if ${A}$ has ${-d}$ as an eigenvalue.
2. Consider the ${L \times L}$ two-dimensional grid graph ${G_{L,L}}$. Let ${n=L^2}$. Prove that

$\displaystyle \lambda_2(G_{L,L}) \asymp \frac{1}{n},$

where ${\lambda_2}$ 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 ${\lambda_2(P_L) \asymp \frac{1}{L^2}}$, where ${P_L}$ is the path on ${L}$ vertices.

3. Let ${n=2^h-1}$ for some integer ${h \geq 1}$. Prove that if ${T_h}$ is the complete binary tree of height ${h}$, we have

$\displaystyle \lambda_2(T_h) \asymp \frac{1}{n},$

where again ${\lambda_2}$ refers to the combinatorial Laplacian.

4. Let ${G}$ be an arbitrary graph. Recall that

$\displaystyle h_G = \min_{|S| \leq n/2} \frac{|E(S)|}{|S|}.$

Let ${\lambda_2}$ be the second eigenvalue of the combinatorial Laplacian on ${G}$.

Prove that,

$\displaystyle \lambda_2 = \min_{f : V \rightarrow \mathbb R} \max_{c \in \mathbb R} \frac{\sum_{u \sim v} |f(u)-f(v)|^2}{\sum_{u \in V} |f(u)-c|^2}\,,$

and

$\displaystyle h_G = \min_{f : V \rightarrow \mathbb R} \max_{c \in \mathbb R} \frac{\sum_{u \sim v} |f(u)-f(v)|}{\sum_{u \in V} |f(u)-c|}\,,$

where both minimums are over non-constant functions.

5. Let ${G}$ be a ${d}$-regular graph and set ${M = \frac12(I+\frac{1}{d} A)}$, where ${A}$ is the adjacency matrix of ${G}$. Let ${\tau = \tau_{\infty}}$ be defined as in the notes for lecture 3. Let ${\mu_1, \mu_2, \ldots, \mu_n}$ be the eigenvalues of ${M}$. Prove that

$\displaystyle \sum_{i=1}^n \mu_i^{2\tau} \leq O(1)\,,$

by evaluating ${\mathrm{tr}(M^{2\tau})}$ in two different ways.