Naor’s *superexpanders* are made using a version of the zigzag product construction. So I thought I should learn more about that. The construction is due to Reingold, Vadhan and Widgerson (reference below).

Suppose we have two graphs \(G_1\) and \(G_2\) related in the following manner:

- \(G_1\) (the “large graph”) has \(N\) vertices and is \(D\)-regular.
- \(G_2\) (the “small graph”) has \(D\) vertices and is \(d\)-regular (note that the number of vertices of the small graph is the same as the regularity of the large graph)
- The edges of \(G_1\) are evenly \(D\)-colored (each vertex has exactly one edge of each color). This assumption is an unnecessary restriction, but it makes explaining the zigzag product easier.

Then the *zigzag product* of \(G_1\) and \(G_2\) is a new graph \(G\) defined as follows: The vertices of \(G\) are pairs \( (v,i) \) where \(v\) is a vertex of \(G_1\) and \(i\) a vertex of \(G_2\) (which is also an edge color for \(G_1\)). The edges of \(G\) are “zigzags” defined by three steps:

- Step one: from \((v,i)\) move to \(v,j\) along an edge of the small graph (“zig”); \(d\) possible choices.
- Step two: from \((v,j)\) move to \((w,j)\), where \(w\) is the neighbor of \(v\) in\(G_1\) along the edge colored \(j\); only one choice.
- Step three: from \((w,j)\) move to \((w,k)\), along an edge of the small graph again (“zag”); \(d\) possible choices.

We see that \(G\) is \(d^2\)-regular on \(ND\) vertices. The main lemma is an eigenvalue bound for the zigzag product. Let \(\lambda(K)\) for a graph \(K\) denote the second-highest eigenvalue of the normalized adjacency matrix. The authors prove

\[ \lambda(G) \le \lambda(G_1) + \lambda(G_2) + \lambda(G_2^2). \]

Thus the zigzag product increases the size of a graph without increasing its least eigenvalue too much, and has degree completely controlled by the small graph. On the other hand one also has the simple construction of *graph squaring*, which squares the adjacency matrix — so it reduces \(\lambda\) and leaves the size alone, but at the cost of greatly increasing degree. Armed with these two constructions and a fixed graph \(H\) with good expansion, one can now give an iterative construction of expander sequences: at each step, one takes the square of the previous step, then takes its zigzag product with \(H\).

**References**

Reingold, Omer, Salil Vadhan, and Avi Wigderson. “Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders.” *Annals of Mathematics* 155, no. 1 (January 1, 2002): 157–187. doi:10.2307/3062153.