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 , , such that each graph is -regular, and the edge-expansion of each graph is at least , for an absolute constant independent of . Ideally, we would like to have such a construction for each , although it is usually enough for most applications that, for some constant and every , there is an for which the construction applies in the interval , or even the interval . We would also like the degree to be slowly growing in and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which and a more complicated one in which .
An explicit construction of a family of expanders is a construction in which is “efficiently computable” given . The weakest sense in which a construction is said to be explicit is when, given , the (adjacency matrix of the) graph can be constructed in time polynomial in . A stronger requirement, which is necessary for several applications, is that given and , the list of neighbors of the -th vertex of can be computed in time polynomial in .
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 be a prime, and define the graph in which , and, for , the vertex is connected to , to and to its multiplicative inverse . The vertex is connected to , to , and has a self-loop. Counting self-loops, the graph is 3-regular: it is the union of a cycle over and of a matching over the vertices ; the vertices , , have a self-loop each. There is a constant such that, for each , the graph has edge expansion at least . Unfortunately, no elementary proof of this fact is known. The graph 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.