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\otimes 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\otimes H)\cdot \hat G \cdot (I_n\otimes 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 \otimes J_D) \hat G (I_n \otimes J_D)\] \[ \quad +~ \gamma_H(1-\gamma_H)(I_n \otimes J_D) \hat G (I_n \otimes E_H)\] \[ \quad +~ (1-\gamma_H)\gamma_H (I_n \otimes E_H) \hat G (I_n \otimes J_D)\] \[ \quad +~(1-\gamma_H)^2(I_n \otimes E_H) \hat G (I_n \otimes E_H).\] All four matrices have eigenvalues at most \(1\). Hence, \[ G \boxtimes H = \gamma_H^2 (I_n \otimes J_D) \hat G (I_n \otimes J_D) + (1-\gamma_H^2) E\] for a matrix \(E\) with eigenvalues at most \(1\).

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

The graph \(G\otimes J_D\) has eigenvalue gap \(\gamma_G=\gamma(G)\). Hence, we can write it as a convex combination \(G\otimes 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\otimes J_D)\hat G(I_n\otimes 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\otimes J_D\), second in \(\hat G\) and third in \((I_n\otimes 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\otimes J_D\).↩