zig-zag product | in theory

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

Continue reading →

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.

Continue reading →

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: zig-zag product

CS294 Lecture 17: Zig-zag Product, continued

CS294 Lecture 16: Zig-Zag Graph Product

CS359G Lecture 17: The Zig-Zag Product

CS359G Lecture 16: Constructions of Expanders