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?