Tag Archives: Cayley graphs

ARV on Abelian Cayley Graphs

Posted on by
2

Continuing from the previous post, we are going to prove the following result: let {G} be a {d}-regular Cayley graph of an Abelian group, {\phi(G)} be the normalized edge expansion of {G}, {ARV(G)} be the value of the ARV semidefinite programming relaxation of sparsest cut on {G} (we will define it below), and {\lambda_2(G)} be the second smallest normalized Laplacian eigenvalue of {G}. Then we have

\displaystyle \lambda_2 (G) \leq O(d) \cdot (ARV (G))^2 \ \ \ \ \ (1)

which, together with the fact that {ARV(G) \leq 2 \phi(G)} and {\phi(G) \leq \sqrt{2 \lambda_2}}, implies the Buser inequality

\displaystyle \lambda_2 (G) \leq O(d) \cdot \phi^2 (G) \ \ \ \ \ (2)

and the approximation bound

\displaystyle \phi(G) \leq O(\sqrt d) \cdot ARV(G) \ \ \ \ \ (3)

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

Continue reading →

CS294 Lecture 15: Abelian Cayley graphs

Posted on by
Reply

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.

Continue reading →

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

Posted on by
1

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 →