CS294 Lecture 17: Zig-zag Product, continued

In which we analyze the zig-zag graph product.

Continue reading

Advertisements

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

Continue reading

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.

Continue reading