Cayley graphs | in theory

In which we show how to find the eigenvalues and eigenvectors of Cayley graphs of Abelian groups, we find tight examples for various results that we proved in earlier lectures, and, along the way, we develop the general theory of harmonic analysis which includes the Fourier transform of periodic functions of a real variable, the discrete Fourier transform of periodic functions of an integer variable, and the Walsh transform of Boolean functions.

Earlier, we prove the Cheeger inequalities

$\displaystyle \frac{\lambda_2}{2} \leq \phi(G) \leq \sqrt{2 \lambda_2}$

and the fact that Fiedler’s algorithm, when given an eigenvector of ${\lambda_2}$ , finds a cut ${(S,V-S)}$ such that ${\phi(S,V-S) \leq 2\sqrt{\phi(G)}}$ . We will show that all such results are tight, up to constants, by proving that

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{\lambda_2}{2} = \phi(G)}$ , showing that the first Cheeger inequality is exactly tight.
The ${n}$ -cycle ${C_n}$ has ${\lambda_2 = O(n^{-2})}$ , and ${\phi(C_n) = \frac 2n}$ , giving an infinite family of graphs for which ${\phi(G) = \Omega(\sqrt{\lambda_2})}$ , showing that the second Cheeger inequality is tight up to a constant.
There is an eigenvector of the 2nd eigenvalue of the hypercube ${H_d}$ , such that Fiedler’s algorithm, given such a vector, outputs a cut ${(S,V-S)}$ of expansion ${\phi(S,V-S) = \Omega(1/\sqrt{d})}$ , showing that the analysis of the Fiedler’s algorithm is tight up to a constant.

In this lecture we will develop some theoretical machinery to find the eigenvalues and eigenvectors of Cayley graphs of finite Abelian groups, a class of graphs that includes the cycle and the hypercube, among several other interesting examples. This theory will also be useful later, as a starting point to talk about constructions of expanders.

For readers familiar with the Fourier analysis of Boolean functions, or the discrete Fourier analysis of functions ${f: {\mathbb Z}/N{\mathbb Z} \rightarrow {\mathbb C}}$ , or the standard Fourier analysis of periodic real functions, this theory will give a more general, and hopefully interesting, way to look at what they already know.