## Lecture 9: Zig-Zag Product

We talked about the zig-zag product today. Let be an -spectral expander and an -spectral expander, respectively. Let’s use to denote the zig-zag product. The graph is an -spectral expander where if and . Moreover, . For better upper-bounds on , see the original zig-zag product paper. For a recent new construction of expanders, see this paper. Perhaps one of you can present this paper.

For each vertex , label all edges incident to arbitrarily by . The product is defined as follows:

- The graph has vertex set .
- There is an edge from to iff there are such that , , and . It is not difficult to see that the product has vertices and degree .

Let be the normalized adjacency matrices of , respectively. Define an matrix where iff . Then, is a symmetric permutation matrix. Now, let (where denote the tensor product of two matrices). Then, it follows that is the normalized adjacency matrix of the product graph . So,

Fix a vector . Define a “collection vector” as follows: . So the th entry of is just the average over all entries in the th “cloud” of the vector . Also define

where is the all-1 vector

Fix a vector , we want to derive something like . So, let’s start with the left hand side. Note that, since is uniform on each “cloud”, we have .

Consider the last term. Since is anti-uniform on each “cloud” (i.e. the sum of ‘s coordinates on each cloud is zero), implying that .

We now bound the second term. Since is a permutation matrix, it does not changes a vector’s norm. We have

Finally, we bound the first term. Relatively straightforward computation leads to

.

Consequently,

Noting that . It is easy to show that

.

Now, suppose we start from a -spectral expander . Let and . It is not difficult to prove by induction that is a -spectral expander.

The zig-zag construction can also be made strongly explicit.

leave a comment