We will describe the zig-zag product of graphs, which allows us to reduce the degree of a graph while approximately maintaining its eigenvalue gap.

Let $$G$$ be a regular graph with $$n$$ vertices and degree $$D$$. (Think of $$n$$ as a growing parameter and $$D$$ as large but absolut constant.)

Let $$H$$ be a regular graph with $$D$$ vertices and degree $$d$$. (Think of $$d$$ as a relatively small absolut constant, e.g., $$d=100$$.)

Suppose that $$H$$ is a very good expander, i.e., eigenvalue gap close to $$1$$. (Since $$H$$ has only constant size and we know that graphs with these properties exist, we could compute $$H$$ efficiently by brute force.)

We will consider graphs with vertex set $$[n]\times [D]$$. We think of this set as $$n$$ disjoint clouds of size $$D$$.

The first graph we consider is $$I_n\otimes H$$, which consists of $$n$$ disjoint copies of $$H$$, one copy per cloud. (The notation $$I_n\otimes H$$ stems from the fact that the random walk matrix of the graph is the tensor product of the matrix $$I_n$$ and the random walk matrix of $$H$$.)

Next, we consider a graph $$\hat G$$ obtained from $$G$$ by splitting every vertex into $$D$$ new vertices, one for each edge. In other words, $$\hat G$$ is a perfect matching on $$[n]\times [D]$$ such that contracting each cloud yields the graph $$G$$.1

The idea of the zig-zag product is to combine the two graphs $$\hat G$$ and $$I_n \otimes H$$ to obtain a graph on $$[n]\times [D]$$ with much smaller degree than $$G$$ but approximately the same eigenvalue gap.

Why should the graphs $$\hat G$$ and $$I_n\otimes H$$ be helpful? One good thing is that both graphs have small degrees. In fact, $$\hat G$$ has only degree $$1$$. Another good thing is that from far away (i.e., if we contract the clouds), the graph $$\hat G$$ looks exactly like $$G$$ (recall that we wanted the new graph to have the same eigenvalue gap as $$G$$). In the zig-zag construction, the graph $$I_n\ot H$$ allows us to effectively contract the clouds, while maintaining small degree.

Definition: The zig-zag product of $$G$$ with $$H$$ is the graph $G\boxtimes H=(I_n\ot H)\cdot \hat G \cdot (I_n\ot H).$

The following lemma shows that $$G\boxtimes H$$ and $$G$$ have the same eigenvalue gap up to a $$\gamma(H)^2$$ factor. (If we choose $$H$$ carefully, then $$\gamma(H)\approx 1$$.)

Lemma: $$\gamma(G\boxtimes H)\ge \gamma(G)\cdot \gamma(H)^2$$.

Proof:

We will use the following useful characterization of the eigenvalue gap: A graph has eigenvalue gap at least $$\gamma$$ if and only if its random walk matrix is a convex combination of the walk matrix of the complete graph and a matrix with largest eigenvalue at most $$1$$ such that the walk matrix of the complete graph has weight at least $$\gamma$$.

Hence, we can write $$H=\gamma_H J_D +(1-\gamma_H)E_H$$ for $$\gamma_H=\gamma(H)$$ and a matrix $$E_H$$ with largest eigenvalue at most $$1$$.

Using this decomposition for $$H$$, we can see that $$G\boxtimes H$$ is a convex combination of four matrices, $G \boxtimes H = \gamma_H^2 (I_n \ot J_D) \hat G (I_n \ot J_D)$ $\quad +~ \gamma_H(1-\gamma_H)(I_n \ot J_D) \hat G (I_n \ot E_H)$ $\quad +~ (1-\gamma_H)\gamma_H (I_n \ot E_H) \hat G (I_n \ot J_D)$ $\quad +~(1-\gamma_H)^2(I_n \ot E_H) \hat G (I_n \ot E_H).$ All four matrices have eigenvalues at most $$1$$. Hence, $G \boxtimes H = \gamma_H^2 (I_n \ot J_D) \hat G (I_n \ot J_D) + (1-\gamma_H^2) E$ for a matrix $$E$$ with eigenvalues at most $$1$$.

How does the graph $$(I_n \ot J_D) \hat G (I_n \ot J_D)$$ look like? We claim that this graph is essentially $$G$$. (The reason is that the multiplications with $$(I_n\ot J_D$$ effectively contract the clouds and we already noted that this contraction makes $$\hat G$$ into $$G$$.) Formally, $$(I_n \ot J_D) \hat G (I_n \ot J_D)=G\ot J_D$$.2

The graph $$G\ot J_D$$ has eigenvalue gap $$\gamma_G=\gamma(G)$$. Hence, we can write it as a convex combination $$G\ot J_D= \gamma_G \cdot J_{Dn} + (1-\gamma_G)E'$$ for a matrix $$E'$$ with eigenvalues at most $$1$$.

It follows that $$G\boxtimes H$$ is a convex combination of the three matrices $$J_{D n}$$, $$E$$, and $$E'$$ (all with eigenvalues at most $$1$$). The matrix $$J_{Dn}$$ has weight $$\gamma_H^2\cdot \gamma_G$$ in this convex combination. Thus, $$G\boxtimes H$$ has eigenvalue gap at least $$\gamma_H^2\cdot \gamma_G$$.

1. A more concrete way to construct $$\hat G$$ from $$G$$ is to map every edge $$e$$ between $$u$$ and $$v$$ in $$G$$ to an edge between to an edge $$\hat e$$ between $$(u,i)$$ and $$(v,i)$$ in $$\hat G$$, where $$i$$ is the index of $$e$$ for $$u$$ and $$j$$ is the index of $$e$$ for $$v$$. (For this construction, we assign an index $$i\in [D]$$ to every edge incident to a vertex $$u\in[n]$$ in $$G$$.)

2. Here is one way to see this identity without “index battle”: How does a random step in the graph $$(I_n\ot J_D)\hat G(I_n\ot J_D)$$ look like? Let $$(v,j)$$ be a random neighbor of a vertex $$(u,i)$$ in this graph. To go from $$(u,i)$$ to $$(v,j)$$ we take a random step first in $$(I_n\ot J_D$$, second in $$\hat G$$ and third in $$(I_n\ot J_D)$$. The third step guarantees that even conditioned on $$u$$, $$v$$, and $$i$$, the distribution of $$j$$ is uniform. What is the distribution of $$v$$ conditioned on $$u$$, $$i$$, and $$j$$? We claim that $$v$$ is just a random neighbor of $$u$$ in $$G$$. The reason is that in the first step we go to a random vertex in the cloud of $$u$$. Every vertex in this cloud uniquely corresponds to one of the outgoing edges of $$u$$. Hence, we selected a random edge out of $$u$$ when taking the second step in $$\hat G$$ (which brings us to the cloud of a random neighbor $$v$$ of $$u$$). It follows that $$(v,j)$$ conditioned on $$(u,i)$$ has the same distribution as in the graph $$G\ot J_D$$.