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. More specifically, the start and endpoints for each edge are at the beginning and end of this "zig-zag-zig" process starting at the points in the replacement product of the two graphs.

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).

Let ${\displaystyle G}$ be a ${\displaystyle D}$-regular graph on ${\displaystyle [N]}$ with rotation map ${\displaystyle \mathrm {Rot} _{G}}$ and let ${\displaystyle H}$ be a ${\displaystyle d}$-regular graph on ${\displaystyle [D]}$ with rotation map ${\displaystyle \mathrm {Rot} _{H}}$. The zig-zag product ${\displaystyle G\circ H}$ is defined to be the ${\displaystyle d^{2}}$-regular graph on ${\displaystyle [N]\times [D]}$ whose rotation map ${\displaystyle \mathrm {Rot} _{G\circ H}}$ is as follows:
${\displaystyle \mathrm {Rot} _{G\circ H}((v,a),(i,j))}$:

It is immediate from the definition of the zigzag product that it transforms a graph ${\displaystyle G}$ to a new graph which is ${\displaystyle d^{2}}$-regular. Thus if ${\displaystyle G}$ is a significantly larger than ${\displaystyle H}$, the zigzag product will reduce the degree of ${\displaystyle G}$. Roughly speaking, by amplifying each vertex of ${\displaystyle G}$ into a cloud of the size of ${\displaystyle H}$ the product in fact splits the edges of each original vertex between the vertices of the cloud that replace it.

The expansion of a graph can be measured by its spectral gap, with an important property of the zigzag product the preservation of the spectral gap. That is, if ${\displaystyle H}$ is a “good enough” expander (has a large spectral gap) then the expansion of the zigzag product is close to the original expansion of ${\displaystyle G}$.

Formally: Define a ${\displaystyle (N,D,\lambda )}$-graph as any ${\displaystyle D}$-regular graph on ${\displaystyle N}$ vertices, whose second largest eigenvalue (of the associated random walk) has absolute value at most ${\displaystyle \lambda }$.

Let ${\displaystyle G_{1}}$ be a ${\displaystyle (N_{1},D_{1},\lambda _{1})}$-graph and ${\displaystyle G_{2}}$ be a ${\displaystyle (D_{1},D_{2},\lambda _{2})}$-graph, then ${\displaystyle G_{1}\circ G_{2}}$ is a ${\displaystyle (N_{1}\cdot D_{1},D_{2}^{2},f(\lambda _{1},\lambda _{2}))}$-graph, where ${\displaystyle f(\lambda _{1},\lambda _{2})<\lambda _{1}+\lambda _{2}+\lambda _{2}^{2}}$.