Zig-zag product

In graph theory, the zig-zag product of regular graphs ${\displaystyle G,H}$, denoted by ${\displaystyle G\circ H}$, is a binary operation which takes a large graph (${\displaystyle G}$) and a small graph (${\displaystyle H}$) and produces a graph that approximately inherits the size of the large one but the degree of the small one. An important property of the zig-zag product is that if ${\displaystyle H}$ is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of ${\displaystyle G}$.

Roughly speaking, the zig-zag product ${\displaystyle G\circ H}$ replaces each vertex of ${\displaystyle G}$ with a copy (cloud) of ${\displaystyle H}$, and connects the vertices by moving a small step (zig) inside a cloud, followed by a big step (zag) between two clouds, and finally performs another small step inside the destination cloud.

The zigzag product was introduced by Reingold, Vadhan & Wigderson (2000). When the zig-zag product was first introduced, it was used for the explicit construction of constant degree expanders and extractors. Later on, the zig-zag product was used in computational complexity theory to prove that symmetric logspace and logspace are equal (Reingold 2008).