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:
- The dimension- hypercube has and , giving an infinite family of graphs for which , showing that the first Cheeger inequality is exactly tight.
- The -cycle has , and , giving an infinite family of graphs for which , showing that the second Cheeger inequality is tight up to a constant.
- There is an eigenvector of the second eigenvalue of the hypercube , such that the SpectralPartitioning algorithm, given such a vector, outputs a cut of expansion , showing that the analysis of the SpectralPartitioning algorithm is tight up to a constant.