# CS294 Lecture 16: Zig-Zag Graph Product

In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A family of expanders is a family of graphs ${G_n = (V_n,E_n)}$, ${|V_n|=n}$, such that each graph is ${d_n}$-regular, and the edge-expansion of each graph is at least ${h}$, for an absolute constant ${h}$ independent of ${n}$. Ideally, we would like to have such a construction for each ${n}$, although it is usually enough for most applications that, for some constant ${c}$ and every ${k}$, there is an ${n}$ for which the construction applies in the interval ${\{ k, k+1, \ldots, ck \}}$, or even the interval ${\{ k, \ldots, ck^c\}}$. We would also like the degree ${d_n}$ to be slowly growing in ${n}$ and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which ${d_n = O(\log^2 n)}$ and a more complicated one in which ${d_n = O(1)}$.

# CS359G Lecture 16: Constructions of Expanders

In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the zig-zag product of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A family of expanders is a family of graphs ${G_n = (V_n,E_n)}$, ${|V_n|=n}$, such that each graph is ${d_n}$-regular, and the edge-expansion of each graph is at least ${h}$, for an absolute constant ${h}$ independent of ${n}$. Ideally, we would like to have such a construction for each ${n}$, although it is usually enough for most applications that, for some constant ${c}$ and every ${k}$, there is an ${n}$ for which the construction applies in the interval ${\{ k, k+1, \ldots, ck \}}$, or even the interval ${\{ k, \ldots, ck^c\}}$. We would also like the degree ${d_n}$ to be slowly growing in ${n}$ and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which ${d_n = O(\log^2 n)}$ and a more complicated one in which ${d_n = O(1)}$.

An explicit construction of a family of expanders is a construction in which ${G_n}$ is “efficiently computable” given ${n}$. The weakest sense in which a construction is said to be explicit is when, given ${n}$, the (adjacency matrix of the) graph ${G_n}$ can be constructed in time polynomial in ${n}$. A stronger requirement, which is necessary for several applications, is that given ${n}$ and ${i\in \{ 1,\ldots,n\}}$, the list of neighbors of the ${i}$-th vertex of ${G_n}$ can be computed in time polynomial in ${\log n}$.

In many explicit constructions of constant-degree expanders, the construction is extremely simple, and besides satisfying the stricter definition of “explicit” above, it is also such that the adjacency list of a vertex is given by a “closed-form formula.” The analysis of such constructions, however, usually requires very sophisticated mathematical tools.

Example 1 Let ${p}$ be a prime, and define the graph ${G_p = (V_p,E_p)}$ in which ${V_p = \{ 0,\ldots,p-1\}}$, and, for ${a\in V_p - \{ 0\}}$, the vertex ${a}$ is connected to ${a+1 \bmod p}$, to ${a-1 \bmod p}$ and to its multiplicative inverse ${a^{-1} \bmod p}$. The vertex ${0}$ is connected to ${1}$, to ${p-1}$, and has a self-loop. Counting self-loops, the graph is 3-regular: it is the union of a cycle over ${V_p}$ and of a matching over the ${p-3}$ vertices ${V_p - \{ 0,1,p-1 \}}$; the vertices ${0}$, ${1}$, ${p-1}$ have a self-loop each. There is a constant ${h>0}$ such that, for each ${p}$, the graph ${G_p}$ has edge expansion at least ${h}$. Unfortunately, no elementary proof of this fact is known. The graph ${G_{59}}$ is shown in the picture below.

Constructions based on the zig-zag graph product, which we shall see next, are more complicated to describe, but much simpler to analyze.

We begin by describing a building block in the construction, which is also an independently interesting construction: a family of expanders with polylogarithmic degree, which have both a very simple description and a very simple analysis.