# 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.

## 7 thoughts on “Homework #1”

1. strstr says:

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

2. Yes. I fixed this in the problem.

3. Cyrus Rashtchian says:

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

4. You’re right, there is a bug..

The optimizations should be $\min \max$. I fixed the problem.

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

5. Kolya Malkin says:

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).

6. Cyrus Rashtchian says:

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.