Recap: The Zig-Zag Product

Given a large graph and a small(er) graph, the zig-zag product of the two graph is a larger graph with degree equal to the size of the small graph squared, which has 2nd largest eigenvalue bounded by the sum of the 2nd largest eigenvalues of the original graphs.

To see what the zig-zag is, we use an intermediate graph, the replacement graph. Note that the degree of G₁ is equal to the number of vertices in G₂. Then the replacement graph G₁ r G₂ consists of replacing each vertex of G₁ with a copy of G₂, so that each vertex in the new graph has all its edges in the local copy of G₂ as well as 1 edge from G₁ which leads to a different copy of G₂.

Then the zig-zag product, G₁ z G₂, has an edge for every path of length 3 in the replacement graph which consists of an edge in a local copy of G₂ followed by an edge from G₁ followed by an edge in the new local copy of G₂. So the degree of a vertex in the zig-zag is the degree of G₂ squared.

Intuitively, the zig-zag works well because if the starting distribution is far from uniform, then the first step in the path of length 3 increases entropy by simply being a step in an expander. If the starting distribution is close to uniform on the component corresponding to the local copies of G₂, then the middle edge in the path of length 3 steals some of the entropy for the first component corresponding to the larger graph G₁, and then the G₂ componenet will be further from uniform so that the third step will increase overall entropy.

The zig-zag product can be iterated to yield an infinite family of expanders where degree remains constant. They are not Ramanujan, since the best possible eigenvalue bound we can get is O(1/D^1/4) for a D-regular expander.