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.