Zig-zag product

Summary

In graph theory, the zig-zag product of regular graphs $G,H$, denoted by $G \circ H$, is a binary operation which takes a large graph ($G$) and a small graph ($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 $H$ is a good expander, then the expansion of the resulting graph is only slightly worse than the expansion of $G$.