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} .]


  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}\,,


    \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. 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?

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s