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.
1. Expanders of Logarithmic Degree
Let be a prime and . We’ll construct a -regular multigraph with vertices. The vertex set of the graph will be the -dimensional vextor space over .
For each vertex , and every two scalars , we have the edges .
In other words, the graph is a Cayley graph of the additive group of , constructed using the generating multiset
Note that the generating set is symmetric, that is, if then (with the same multiplicity), and so the resulting multigraph is undirected.
Let be the adjacency matrix of and be the normalized adjacency matrix. We will prove the following bound on the eigenvalues of .
Theorem 1 For every prime and every , if we let be the eigenvalues of with multiplicities, then, for every
For example, setting gives us a family of graphs such that for each graph in the family, and hence , and the number of vertices is , while the degree is , meaning the degree is .
Proof: We will compute the eigenvalues of the adjacency matrix of , and prove that, except the largest one which is , all the others are non-negative and at most .
Recall our characterization of the eigenvalues of the adjacency matrix of a Cayley multigraph of an abelian group with generating multiset : we have one eigenvector for each character of the group, and the corresponding eigenvalue is .
What are the characters of the additive group of ? It is the product of copies of the additive group of , or, equivalently, the product of copies of the cyclic group . Following our rules for constructing the character of the cyclic group and of products of groups, we see that the additive group of has one character for each , and the corresponding character is
where
Thus, for each , we have an eigenvalue
When then the corresponding character is always equal to one, and the corresponding eigenvalue is .
Now consider any , and define the polynomial . Note that it is a non-zero polynomial of degree at most , and so it has at most roots. The eigenvalue corresponding to is
where we use the fact that, for every , the sum equals zero, since it is the sum of the values of the non-trivial character , and we proved that, for every non-trivial character, the sum is zero.
In conclusion, we have
2. The Zig-Zag Graph Product
Given a regular graph with normalized adjacency matrix , if are the eigenvalues of with multiplicities we define
In particular, , and if we are able to construct a family of graphs such that is at most a fixed constant bounded away from one, then we have a family of expanders. (Our construction will be inductive and, as often happens with inductive proofs, it will be easier to maintain this stronger property than the property that is bounded away from one.)
Given graphs and of compatible sizes, with small degree and large edge expansion, the zig zag product is a method of constructing a larger graph also with small degree and large edge expansion.
If:
- a -regular graph on vertices, with
- a -regular graph on vertices, with
Then:
- a -regular graph on vertices, with .
We will see the construction and analysis of the zig zag product in the next lecture.
For the remainder of today, we’ll see how to use the zig zag product to construct arbitrarily large graphs of fixed degree with large edge expansion.
Fix a large enough constant . ( will do.) Construct a -regular graph on vertices with . (For example is a degree graph on vertices with .)
For any graph , let represent the graph on the same vertex set whose edges are the paths of length two in . Thus is the graph whose adjacency matrix is the square of the adjacency matrix of . Note that if is -regular then is -regular
Using the from above we’ll construct inductively, a family of progressively larger graphs, all of which are -regular and have .
Let . For let .
Theorem 2 For each , has degree and .
Proof: We’ll prove this by induction.
Base case: is -regular. Also, .
Inductive step: Assume the statement for , that is, has degree and . Then has degree , so that the product is defined. Moreover, . Applying the construction, we get that has degree and This completes the proof.
Finally note that has vertices.
Typo in the title: should be CS359G. =)
or, maybe I am actually teaching three courses this term
Luca, thank you for these notes. I am working on my doctorate (in EE not TCS) and these notes are extremely helpful for me to fill in the holes in my education.
> Unfortunately, no elementary proof of this fact is known.
Doesn’t this follow easily from Bourgain-Gamburd, which is based on elementary work?