CS359G Lecture 6: The Spectrum of the Cycle and of the Hypercube

In which we talk about the spectrum of Cayley graphs of abelian groups, we compute the eigenvalues and eigenvectors of the cycle and of the hypercube, and we verify the tightness of the Cheeger inequalities and of the analysis of spectral partitioning

In this lecture we will prove the following results:

  1. The dimension-{d} hypercube {H_d} has {\lambda_2 = 1- \frac 2d} and {h(H_d) = \frac 1d}, giving an infinite family of graphs for which {\frac{1-\lambda_2}{2} = h(G)}, showing that the first Cheeger inequality is exactly tight.
  2. The {n}-cycle {C_n} has {\lambda_2 = 1 - O(n^{-2})}, and {h(C_n) \geq \frac 2n}, giving an infinite family of graphs for which {h(G) = \Omega(\sqrt{1-\lambda_2})}, showing that the second Cheeger inequality is tight up to a constant.
  3. There is an eigenvector of the second eigenvalue of the hypercube {H_d}, such that the SpectralPartitioning algorithm, given such a vector, outputs a cut {(S,V-S)} of expansion {h(S) = \Omega(1/\sqrt{d})}, showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.

Continue reading

Advertisements