Authors Eyal Rozenman, Aner Shalev, Avi Wigderson,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120
http://theoryofcomputing.org
Iterative Construction of Cayley Expander
Graphs
Eyal Rozenman∗ Aner Shalev† Avi Wigderson‡
Received: August 4, 2005; published: April 25, 2006.
Abstract: We construct a sequence of groups Gn , and explicit sets of generators Yn ⊂ Gn ,
such that all generating sets have bounded size, and the associated Cayley graphs are all
expanders. The group G1 is the alternating group Ad , the set of even permutations on the
elements {1, 2, . . . , d}. The group Gn is the group of all even symmetries of the rooted
d-regular tree of depth n. Our results hold for any large enough d.
We also describe a finitely generated infinite group G∞ with generating set Y∞ , given
with a mapping fn from G∞ to Gn for every n, which sends Y∞ to Yn . In particular, under the
assumption described above, G∞ has property (τ) with respect to the family of subgroups
ker( fn ).
The proof is elementary, using only simple combinatorics and linear algebra. The re-
cursive structure of the groups Gn (iterated wreath products of the alternating group Ad )
allows for an inductive proof of expansion, using the group theoretic analogue (of Alon et
∗ The Hebrew university, Jerusalem. E-mail: eyalroz@cs.huji.ac.il. Part of this research was performed while visiting
the Institute for Advanced Study, Princeton, NJ.
† The Hebrew university, Jerusalem. E-mail: shalev@math.huji.ac.il. Partially supported by BSF grant 2000-53 and a
grant from the Israel Science Foundation.
‡ Institute for Advanced Study, Princeton. E-mail: avi@ias.edu. Partially supported by NSF grant CCR-0324906.
ACM Classification: G.2.2, G.3
AMS Classification: 05C25, 37A30
Key words and phrases: Cayley graphs, Expanders, Expander graphs, Wreath products
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2006 Eyal Rozenman, Aner Shalev, and Avi Wigderson DOI: 10.4086/toc.2006.v002a005
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
al., 2001) of the zig-zag graph product (Reingold et al., 2002). The basis of the inductive
proof is a recent result by Kassabov (2005) on expanding generating sets for the group Ad .
Essential use is made of the fact that our groups have the commutator property: ev-
ery element is a commutator. We prove that direct products of such groups are expanding
even with highly correlated tuples of generators. Equivalently, highly dependent random
walks on several copies of these groups converge to stationarity on all of them essentially
as quickly as independent random walks. Moreover, our explicit construction of the gen-
erating sets Yn above uses an efficient algorithm for solving certain equations over these
groups, which relies on the work of Nikolov (2003) on the commutator width of perfect
groups.
1 Introduction
1.1 Expander graphs
Expanders are graphs which are sparse but nevertheless highly connected. Expanders graphs have been
used to solve many fundamental problems in computer science, in topics including network design (e.g.
[40, 41, 1]), complexity theory ([49, 44, 48]), derandomization ([36, 18, 19]), coding theory ([45, 46]),
and cryptography ([15]). Expander graphs have also found some applications in various areas of pure
mathematics, such as topology, measure theory, game theory and group theory (e.g. [21, 30, 16, 31]).
Standard probabilistic arguments ([39]) show that almost every constant-degree (≥ 3) graph is an
expander. However, most applications demand explicit constructions. Here we take the most stringent
definition of explicitness of an infinite family of graphs, requiring that a deterministic polynomial time
algorithm can compute the neighbors of any given vertex, from the vertex name and the index of the
graph in the family. This challenge of explicit construction led to an exciting and extensive body of
research.
Most of this work was guided by the algebraic characterization of expanders, developed in [47, 5, 2].
They showed the intimate relation of (appropriate quantitative versions of) the combinatorial (isoperi-
metric) notion of expansion above, to the spectral gap in the adjacency matrix (or, almost equivalently,
the Laplacian) of the graph. This relationship is tight enough for almost all applications (but there are
some exceptions, e.g. see [50, 10]).
Using this connection, an infinite family of regular graphs is defined to be an expander family if
for all of them the second largest eigenvalue of the normalized adjacency (i.e. random walk) matrix is
bounded above by the same constant that is smaller than 1.
This algebraic definition of expanders by eigenvalues naturally led researchers to consider algebraic
constructions where this eigenvalue can be estimated. The celebrated sequence of papers [32, 14, 5,
3, 20, 29, 33, 35] provided such highly explicit families of constant-degree expanders. All of these
constructions are based on groups, and their analysis often appeals to deep results in mathematics.
The algebraic mould was broken recently by [42], where a simple, combinatorial construction of
constant-degree expander graphs was presented. The construction is iterative, generating the next graph
in the family from two previous ones via a novel graph product, the zig-zag product. This product was
proved (using simple linear algebra) to simultaneously keep the degree small, and retain expansion.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 92
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
Thus the iteration process need only be provided with an initial, fixed size expander “seed” graph, from
which all others are generated. The required parameters of the seed graph are easily shown to hold for a
random graph (which suffices for explicitness - it is of constant size), but it is also easy to construct one
explicitly.
Our main result in this paper is a similar iterative construction of expanding Cayley graphs (which
we turn to define next) from one initial “seed” Cayley graph. In our case, the seed Cayley graph is
based on the group Ad , the group of even permutations on the set {1, 2, . . . , d}. In a recent breakthrough,
Kassabov [22] explicitly constructed a bounded-size, expanding generating set for Ad , which yields the
seed expander Cayley graph we need.
Our construction may be seen as another step in exploring this fundamental notion of expansion, and
its relations to yet unexplored mathematical structures. It also further explores the power of the zig-zag
product in constructing even stronger expanders. It was already shown [10] that it can yield expansion
beyond the eigenvalue bound, and is shown here to yield Cayley expanders.
1.2 Expanding Cayley graphs
For a finite group H and a (symmetric) set of elements T in it, the Cayley graph C(H; T ) has the elements
of H as vertices, and edges connect a pair of vertices g, h if their “ratio” gh−1 is in T . We remark that
while most applications do not require the expanders to be “Cayley”, the recent paper [7] seems to
essentially require Cayley expanders to achieve nearly linear-sized locally testable codes (LTCs) and
probabilistically checkable proof (PCPs).
Many of the algebraic expander constructions mentioned above are Cayley graphs. In all of these, the
groups in question are linear matrix groups over finite fields, and their expansion follows from celebrated
results in mathematics, including Kazhdan’s work on Property T [25], Selberg’s 3/16 theorem [43], and
the resolution of the Ramanujan conjecture of Eichler, Deligne and Igusa (starting in [12]). It should be
noted that for some of the other algebraic constructions elementary proof of expansion exist, using only
a discrete Fourier transform [20].
For other natural families of groups the question was considered both by mathematicians and com-
puter scientists. For example, for Abelian groups it is easy to see that any set of expanding generators
has to be at least logarithmic in the size of the group. Thus they cannot provide expanding Cayley graphs
of constant degree (a more general result appears in [26]). Lubotzky and Weiss generalized this negative
result for all solvable groups of bounded derived length [28].
Understanding which natural families of groups can be made expanding (with a fixed size generating
set) is a basic question, and little progress was made over the foundational results above in the last 15
years. However, in the last year several breakthroughs were made by Kassabov and Nikolov [22, 23, 24].
These results suggest that all the simple groups may have fixed size expanding generating sets. Of
particular interest to our work is the family of symmetric groups (of all permutations). Much work has
been devoted to analyzing the expansion of this group under a variety of generating sets in the context
of card shuffling (e.g. see [11, 27]). However, in all these papers the generating sets are huge, and did
not provide a clue to the status of this problem. In a recent breakthrough, Kassabov [22] showed that the
symmetric groups indeed have explicit, fixed-size expanding generators, independent on the group size.
The possibility that the zig-zag product and iterative construction may be used for Cayley expanders
was first revealed in [4]. They discovered that the well-known semi-direct product on groups may be
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 93
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
viewed (roughly speaking) as a special case of the zig-zag product of graphs. More precisely, the zig-
zag product of two Cayley graphs, with certain important restrictions on the structure of their generating
sets, is a Cayley graph of the semi-direct product of the associated groups. Thus one can generate larger
Cayley expanders of small degree from smaller ones. This observation was used to show that expansion
is not a group property – in some groups certain constant size sets will expand, while others will not.
This Cayley graph version of the zig-zag theorem raises the hope that, given a “seed” expander
Cayley graph, one can obtain a sequence of expander Cayley graphs via an iterative process using the
zig-zag theorem. However, unlike the case of unstructured graphs, the restrictions on generators alluded
to above for applying the zig-zag product on Cayley graphs, make iterations a highly nontrivial (and
illuminating) task. In [34] such a construction was given, which falls short of the task at hand on two
counts. First, the generating sets (and hence the degrees) of the groups in the family are not of constant
size, but rather grow slowly (roughly like log∗ of the group size). Second, these generating sets are shown
to exist via a probabilistic argument, hence the resulting family is not explicit. Still, this construction
makes no assumptions, as the seed Cayley expander for the iteration is easily seen to exist.
In this paper we fix both problems. We give a sequence of groups Gn , and explicit generating sets
Yn for each Gn , such that the Cayley graphs C(Gn ,Yn ) are expanding. Moreover, Yn as bounded size,
independent of n. Actually, we will later on see that the generators Yn are consistent with each other: In
the natural projection of Gn+1 to Gn the set Yn+1 projects to the set Yn .
The technique developed yields some results which do not require a seed Cayley graph at all. We
show how to obtain an explicit sequence of expanding Schreier graphs. (The novelty is in the explicit-
ness, since by [17] every regular graph with even degree is a Schreier graph). We then use the Schreier
graph sequence to construct a sequence of expanders Xn in which each graph Xn+1 is a lift of Xn , by
noticing that in our Schreier graph sequence each graph is actually a lift of its predecessor (lifts are
defined in Section 9).
1.3 Our construction
Our groups are completely different from most groups previously used in this area. Indeed, they are very
natural combinatorial objects. Let T (d, n) denote the d-regular tree of depth n. The group of symmetries
of this tree allows permuting the children of every internal node arbitrarily. Thus every element of this
group may be described by a mapping of the internal nodes to the symmetric group Sd , describing how
to permute the children of every such node. Group product of two such elements is simply performing
the first set of permutations at every node, and then the next set. Our groups Gn are subgroups of all
symmetries, allowing only even permutations at every internal node of T (d, n). This natural restriction
avoids a huge Abelian quotient that would have rendered expansion impossible, as the group would
not even be generated by a constant number of generators. Our method of proof (sketched below) is
elementary, using only linear algebra. All other known proofs use representation theory of the groups
involved, and in most cases much deeper results as well.
There is a very natural inductive definition of the groups Gn . G1 is the alternating group Ad of
all even permutations on d elements (and is essentially the “seed group” of our construction). Gn+1
can be obtained from d copies of Gn , and one copy of Ad acting on them simply by permuting the
copies. Formally, this is called a wreath product, denoted Gn+1 = Gn o Ad , and is a special case of a
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 94
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
semidirect product, giving equivalently Gn+1 = (Gn )d o Ad . Our assumption gives a small expanding
set of generators for Ad , and by induction we have such a set for Gn .
How does induction proceed? Naturally, we would like to use the zig-zag theorem for the semi-direct
product [4, 42]. The technical requirement alluded to above is simply that we find an expanding gener-
ating set for (Gn )d , which need not be small, but must be an orbit under the action of Ad , given a (small)
expanding generating set Yn for Gn . A natural candidate for such an orbit is all (even) permutations of the
balanced d-vector, one which has every one of the elements of Yn occurring the same number of times
(if |Yn | divides d). It is the largest possible orbit, and the projection of a random element of the orbit to
any small subset of the coordinates is (almost) a random independent element of Yn in each coordinate.
We now turn to study the second eigenvalue of the Cayley graph of (Gn )d under these generators. The
associated linear operator acts on the space of real functions on (Gn )d . Luckily, this space of functions
is simple to describe - it is the d-fold tensor product of the same space for Gn . What is not so lucky is
the dependence between the coordinates of a balanced vector. Indeed, had Gn been Abelian, this orbit
would not even be generating (i.e. the graph would not be connected). Here our special group structure
is important. A key fact (proved by Nikolov [37]) is that every element in Gn is a commutator. Construct
a new generating set Ỹn by adding to Yn , for each of its elements, the constituents of its representation
as a commutator. We use Nikolov’s proof to actually give a polynomial time algorithm for finding this
representation. Now take the orbit of all balanced vectors over Ỹn to be the generating set for (Gn )d .
How can this revision take care of the dependencies? A simpler setting, to which we reduce our
analysis, is the following Cayley graph. The group is simply (Gn )2 , namely only two copies of Gn .
The generators are all pairs (g, g−1 ) for all g ∈ Ỹn . Thus, there is complete correlation between the two
coordinates. The key point is that, using the special structure of Ỹn , with positive probability a short
word in one of the two components will vanish, while in the second it will give an original generator of
Yn , thereby decoupling the dependence of the two components. So, quite surprisingly, this Cayley graph
on two copies is expanding despite the complete correlation (it is a nontrivial exercise to even establish
connectivity of this graph – note that it would not be connected had Gn been Abelian, or if we took
instead the pairs (g, g) for any group Gn ). This construction (which we feel is of independent interest) is
quite special and mysterious, and naturally the description above hides many essential details. Still, it is
the heart of the matter.
For m ≥ n there is a natural restriction map Gm → Gn - given a symmetry of the tree with depth
m consider its action on the subtree with depth n with the same root. As we shall see, the generating
set Ym is mapped to Yn under this restriction. This gives rise to an infinite “limit group” G∞ given
with a generating set Y∞ and restriction maps fn : G∞ → Gn , where fn (Y∞ ) = Yn . In particular, under
the assumption on Ad , the group G∞ has property (τ) with respect to the family of subgroups ker( fn )
(Lubotzky’s property (τ), a “baby” version of Kazhdan’s property (T), is defined in Section 8).
1.4 Organization of this paper
In Section 2 we define expander graphs and Cayley graphs, and present some useful results. In Section 3
we define the sequence of groups we use. In Section 4 we describe the expanding generating sets, and
prove the main Theorem 4.1 - that they are indeed expanding - by induction. The proof is based on a
main lemma (Theorem 4.6). The lemma gives an expanding generating set for the group Gd given an
expanding generating set for G (under certain conditions on G). Finally, in Section 6 we present an
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 95
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
algorithmic version of Nikolov’s theorem, that every element in our family of groups has a commutator
representation that can be found efficiently.
We then turn to some corollaries of the main theorem. In Section 7 we explicitly construct a sequence
of expanding Schreier graphs, free from the seed graph on the alternating group. In Section 8 we give
generators for a subgroup of the symmetry group of the infinite rooted d-regular tree. These generators,
when restricted to the finite rooted d-regular tree with depth n, generate an expander Cayley graph on the
(alternating) group of symmetries of this finite tree. As a corollary we deduce that this infinite group has
Lubotzky’s Property (τ) with respect to a natural infinite family of normal subgroups. Then in Section 9
we combine the previous two results to obtain a sequence of expanding graphs each of which is a lift of
the previous one.
2 Preliminaries
2.1 Graphs, eigenvalues and adjacency matrices
All graphs discussed in this paper are undirected, regular graphs. We allow multiple edges and self
loops, so graphs are best understood as symmetric nonnegative integer matrices with a fixed row-sum,
called the degree. For a graph X, we let V (X) denote its set of vertices and E(X) its (multiset of) edges.
Let X be a k-regular graph, and M = MX its normalized adjacency matrix (divide the adjacency
matrix by the degree k to make it stochastic). We denote by λ (X) the second largest (in absolute value)
eigenvalue of M. The spectral gap of the graph is 1 − λ (X).
Let W be the vector space of real functions on the set V (X), with its standard L2 inner product. MX
defines a linear operator on W : For f ∈ W , the value of the function MX ( f ) ∈ W on a vertex x is the
average value of f on all the neighbors of x (counted with multiplicities).
Let W|| be the one-dimensional subspace consisting of the constant functions, and let W⊥ be the or-
thogonal complement. Since the constant functions are eigenvectors of M corresponding to the (largest)
eigenvalue 1, then
λ (X) = max kMwk/kwk
w∈W⊥
where kwk is the L2 norm of w.
Definition 2.1. An infinite family of graphs Xn is called an expander family if λ (Xn ) ≤ µ for some
µ < 1 independent of n. The family is said to be (strongly) explicitly described, if there is a polynomial
time algorithm which, on input n and the name of a vertex v in Gn (in binary), outputs the neighbors of
v in Gn .
We will use the following two simple results, which describe how taking the tensor power of a graph,
and taking the power of a graph, affect the 2nd eigenvalue λ :
Claim 2.2. Let X = (V, E) be a graph, and let MX be the normalized adjacency matrix. Let MY =
(MX )⊗d , and define Y to be the graph (on the vertex set V d ) with normalized adjacency matrix MY . Then
λ (Y) = λ (X).
Observation 2.3. Let X = (V, E) be a graph, MX the normalized adjacency matrix and MY = (MX )k .
Let Y be the graph (on vertex set V ) with normalized adjacency matrix MY . Then λ (Y) = λ (X)k .
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 96
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
We will use the following convexity result later: If the spectral gap (1 − λ (Y)) of a graph Y is not
too small, and Y is a large subgraph of X (on the same vertex set) then the spectral gap of X is also not
too small.
Claim 2.4. Let Y = (V, E1 ) ⊂ X = (V, E2 ) (i.e. E1 ⊂ E2 ) be s- and t-regular graphs respectively on the
same vertex set V . Then
s
1 − λ (X) ≥ (1 − λ (Y)) .
t
We will later need the following result on vectors
Claim 2.5. If for some vectors w0 , w1 , . . . , wL , all with norm 1,
L
(1/L) · k ∑ wi k ≤ 1 − ε
i=1
then
L
(1/L) · ∑ kw0 + wi k/2 ≤ 1 − ε/4 .
i=1
2.2 Groups and the wreath product
2.2.1 Cayley graphs
Let G be a finite group. We will represent groups multiplicatively, and 1 will denote the identity element
of the group. Let Y be a multi-subset of G. We will always use symmetric sets Y , namely the number
of occurrences of x and x−1 in Y is the same for every x ∈ G. |Y | will denote the size of the multiset
(counting multiplicities).
The Cayley graph C(G,Y ) has vertex set G, and for every vertex g ∈ G and x ∈ Y there is an edge
(g, gx). The graph C(G,Y ) is undirected (as Y is symmetric) and is |Y |-regular. For x ∈ G let Px be
the permutation matrix corresponding to g → gx in G. The normalized adjacency matrix of C(G,Y ) is
∑x∈Y Px /|Y |. We will also use the notation Ex∈Y [Px ] to denote this average of operators.
Let W = W (G) be the vector space of functions G → R as in the previous section. We will be
interested in the expansion properties of Cayley graphs on the group Gd , the Cartesian product of d
copies of G. Note that W (Gd ) = W ⊗d .
Observation 2.6. Let W|| be the space of constant functions on the vertices of G, and let W⊥ be its
orthogonal complement. Let b̄ = (b1 , . . . , bd ) be a length-d vector in the alphabet {||, ⊥}, and let Wb̄ be
the vector space ⊗di=1Wbi . Consider the space W ⊗d , the d-th tensor power of W . The space W ⊗d inherits
an inner product structure from W , where the inner product of two pure tensors is the product of the
inner products of the components of the tensors. The orthogonal decomposition W = W|| +W⊥ induces
an orthogonal decomposition
W ⊗d = ∑ Wb̄
b̄∈{||,⊥}d
to 2d subspaces by the distributive law for tensor products. For any x ∈ Gd the operator Px preserves the
decomposition.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 97
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
Corollary 2.7. For any Cayley graph C(Gd , Ȳ ), the normalized adjacency operator Ex∈Ȳ [Px ] preserves
the given decomposition of W ⊗d , so
λ (Gd , Ȳ ) = max max k E [Px (w)]k/kwk .
b̄6=||d w∈Wb̄ x∈Ȳ
That is, it suffices to bound k Ex∈Ȳ [Px (w)]k from above, for vectors w that are purely in one of these
2d − 1 subspaces.
The following two observations describe cases where we can ignore part of the coordinates of x ∈ Gd
when trying to estimate k Ex∈Ȳ [Px (w)]k.
Observation 2.8. Let b̄ = b1 , . . . , bd where bi =⊥ for i ≤ r and bi = || otherwise. For w ∈ Wb̄ = W⊥⊗r ⊗
⊗(d−r)
W|| , the value of Px (w) does not depend on xr+1 , . . . , xd .
Proof. w is a real function on Gd . The statement that w ∈ Wb̄ and bi = || means that w does not depend
on the i-th coordinate of its input.
Observation 2.9. Let X̄ ⊂ Gd be a set of group elements whose last d − r coordinates constitute some
fixed vector x̄ ∈ Gd−r . Then for every w ∈ W ⊗d the value of
k E [Px (w)]k
x∈X̄
does not depend on x̄.
Observation 2.3 from Section 2.1 translates nicely to the Cayley graph world
Observation 2.10. Let G be a group, Y ⊂ G. Define Z to be the set of all words of length k in Y . Then
λ (G, Z) = λ (G,Y )k .
We end with an observation which simplifies the proof of explicitness for families of Cayley graphs.
Observation 2.11. A family of Cayley graphs C(Gn ,Yn ) is explicit if there are polynomial time algo-
rithms in log |Gn | for
• performing group multiplication in Gn ,
• computing inverses in Gn , and
• computing the set Yn .
2.2.2 Wreath products and the zig-zag product
Let A and B be finite groups. Assume that B ⊂ Sd , that is, it acts by permutations on the set [d] =
{1, . . . , d}. Define the wreath product 1 A o B of A and B to be the group whose elements are vectors
(a1 , . . . , ad , σ ), where ai ∈ A for all i, and σ ∈ B. The group multiplication rule is
(a1 , . . . , ad , σ ) · (ã1 , . . . , ãd , τ) = (aτ(1) ã1 , . . . , aτ(d) ãd , σ τ) .
1 More precisely, this is referred to as the permutational wreath product in the literature.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 98
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
One can check that this defines a group structure on A o B. The wreath product is a special case of a more
general construction - it is the semi-direct product of Ad and B, where Ad is the Cartesian product of d
copies of A. The groups Ad , B are naturally embedded in A o B, and we will sometimes refer to elements
of Ad and B as elements of A o B.
Let α ⊂ Ad , β ⊂ B be sets of generators. Suppose α has a special structure: it is a single B-orbit.
This means that for some arbitrary ā ∈ α, the set α consists of all vectors obtained from ā by permuting
its coordinates by a permutation in B. We now define a set γ in A o B by γ = {xāy | x, y ∈ β }. One can
check that γ generates A o B. The following theorem from [4], following the zig-zag theorem of [42],
shows that if α, β are sufficiently good expanding generators then so is γ.
Theorem 2.12. [4] If α is a single B-orbit then λ (A o B, γ) ≤ λ (Ad , α) + λ (B, β ).
Note that |γ| = |β |2 depends only on the size of β , while α could be large (it could be as large as
|B|). Also, it is easy to compute γ given α and β , as multiplications in A o B can be computed efficiently.
2.2.3 The commutator property
Let A be a group. For g, h ∈ A define the commutator [g, h] to be ghg−1 h−1 . A has the commutator
property if for every element a ∈ A there is a solution in the variables x, y to the equation a = [x, y]. (Note
that this is a stronger property than just the commutator subgroup [A, A] being equal to A.) Nikolov [37]
proves
Theorem 2.13. [37] Let A be a group, and B ⊂ Sd a group of permutations. If A, B have the commutator
property then so does A o B.
We shall need an algorithmic version of this theorem. For a group A, a commutator representation
algorithm gives, for an input a ∈ A, some pair x, y ∈ A such that a = [x, y].
Theorem 2.14. Let A, B be as in Theorem 2.13. Suppose we are given commutator representation al-
gorithms for the groups A, B. Then we obtain such an algorithm for A o B. This algorithm calls the
algorithm on B one time, and the algorithm on A at most d times, and uses at most O(d) extra multipli-
cation operations on A, B. (The description of the algorithm appears in the proof of the theorem.)
We prove the theorem in Section 6.
3 Overview of the construction
In Section 3.1 we will define our sequence of groups Gn . In Section 4 we will show how to find gen-
erating subsets Yn ⊂ Gn that give λ (Gn ,Yn ) < 1/1000 with bounded size |Y1 |4 . This will be based
on the assumption that there exists a small enough subset Y1 of the alternating group Ad such that
λ (Ad ,Y1 ) < 1/1000.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 99
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
3.1 The family of groups
Definition 3.1. The groups in our construction are defined by G1 = Ad and, inductively, Gn+1 = Gn o Ad .
Another way to view the group Gn is as a subgroup of the full group of symmetries of the d-regular,
depth n tree (by d-regularity here we mean that each inner vertex has d descendants). Each element
in the group of symmetries is uniquely defined by writing a permutation on each internal node of the
tree, indicating how the children of this vertex are permuted. In the subgroup Gn all these permutations
should be even. The representation of an element of Gn as a list of even permutations is polynomial in
log |Gn |. Multiplying two elements and inverting an element can be done in time which is polynomial in
the size of this representation
The following important corollary of Theorem 2.14 shows that for our groups Gn there is an efficient
commutator representation algorithm.
Lemma 3.2. If d ≥ 5 then the groups Gn have the commutator property of Section 2.2.3. Moreover, Gn
has a commutator representation algorithm that runs in time polynomial in log |Gn |.
Proof. G1 = Ad , and by [38] it has the commutator property. By induction, using Theorem 2.13, every
Gn has the commutator property. The existence of an efficient commutator representation algorithm
follows from Theorem 2.14. Full details are given in Section 6.
4 Main theorem
Theorem 4.1. Suppose that for some d there exists a set of generators Y1 ⊂ Ad such that λ (Ad ,Y1 ) <
1/1000 and |Y1 | ≤ d 1/28 /1040 . Then there exist sets Yn ⊂ Gn such that λ (Gn ,Yn ) < 1/1000 and |Yn | ≤
d 1/7 /1040 . Furthermore, Yn can be computed in time polynomial in log |Gn |.
The graphs C(Gn ,Yn ) are the required sequence of Cayley graphs. The sets Yn can be computed
efficiently, and we saw in Section 3.1 that group operations in Gn can also be computed efficiently, so
by Observation 2.11 this is an explicit family of Cayley graphs.
The assumption of the theorem is true for very large d:
Theorem 4.2 ([22]). For every integer d ≥ 0 there exists a subset Ud of the symmetric group Sd such
7
that |Ud | ≤ 1010 and λ (Sd ,Ud ) ≤ 1/1000.
9
Corollary 4.3. If d ≥ 1010 Then the conditions of Theorem 4.1 hold.
We will construct the expanding generators Yn ⊂ Gn inductively. The basis of the induction is the
assumption in the theorem about G1 = Ad .
Let G = Gn . We are given Y ⊂ G such that λ (G,Y ) < 1/1000 and |Y | ≤ d 1/7 /1040 . We want to
find a set Y 0 ⊂ G o Ad such that λ (G o Ad ,Y 0 ) < 1/1000 and |Y 0 | ≤ d 1/7 /1040 . We will use Theorem 2.12.
The theorem requires an expanding generating set for Ad (which we already have), and an expanding
generating set T ⊂ Gd which is a single Ad -orbit. Given any element of such T , Theorem 2.12 produces
(explicitly) an expanding generating set for G o Ad = Gn+1 .
Can we find an expanding, single-orbit, generating set for Gd ? Here is a simple attempt that fails.
Take T = Y d . The set Y d is expanding, as λ (Gd ,Y d ) = λ (G,Y ) by Claim 2.2. Unfortunately, Y d contains
exponentially many Ad -orbits. Another natural set to consider in Gd is the set of balanced vectors:
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 100
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
Definition 4.4. Let G be a group, and Y ⊂ G. For d > |Y |, define Y (d) to be the vectors in Y d in which
every u ∈ Y appears exactly bd/|Y |c times, and the rest of the elements are 1 ∈ G. We call these vectors
balanced vectors. Every two elements in the set Y (d) are equal up to a permutation of the coordinates.
Since d > |Y | we may assume that the permutation is even. In other words, the set Y (d) is a single
Ad -orbit.
The set Y (d) looks promising, but is it expanding? Not always. If G is Abelian, Y (d) does not even
generate Gd , since every element in Y (d) has product of coordinates equal to 1 (Y is symmetric, and every
element of Y appears the same number of times in Y (d) ). The groups Gn are far from being Abelian.
Indeed, every element of Gn has a representation as a commutator. It turns out that this property, along
with the existence of a small generating set Y for G (assumed by induction) enables us to find a good
generating set for Gd . We will enlarge Y somewhat to a set X ⊃ Y , and see that X (d) is expanding for
Gd .
Definition 4.5. Let G be a group, and let Y ⊂ G. Suppose every element y ∈ Y can be written as a
commutator in G, namely y = ay by a−1 −1
y by for some ay , by ∈ G. Define
Y∗ = {ay , by , a−1 −1 −1 −1
[
y , by , ay by , by ay } ∪ {1} .
y∈Y
Y ∗ is symmetric, and |Y ∗ | ≤ 7|Y |.
Theorem 4.6. Let G be a group. Suppose that every element of Y is a commutator in G. Let c, k ∈ N be
constants (to be chosen later). Define c ·Y ⊂ G to be the multi-subset where every element of Y appears
c times. Define X = (c ·Y ) ∪Y ∗ , and λ = λ (G,Y ). If d ≥ k2 · |X|7 then
n 6
o
λ (Gd , X (d) ) < 0.01 + max (λ + 7/c), e−kc(1−λ )/10
where X (d) is the set of balanced vectors.
The proof is given in Section 5. To get a feeling for the constants, note that the larger k and c are,
the better inequality we get in the theorem. k is large when X is small. c is large when X is much larger
that Y , so k gets smaller when c gets larger. Nevertheless, it is not difficult to make both of them large
enough for our purposes.
Theorem 4.6 is the required result for the inductive step - it remains to show that we can choose c, k
properly such that λ (Gd , X (d) ) is small enough for Theorem 2.12.
We proceed with the inductive step. We are given a set Yn ⊂ Gn of size at most |Y1 |4 such that
λ (Gn ,Yn ) < 1/1000. Apply Theorem 4.6 (with c = 103 , k = 105 ). Then the conditions of Theorem 4.6
hold, and we obtain a set X (d) ⊂ Gd such that λ (G, X (d) ) < 1/50 (just substitute our k, c in the theorem
to see this). Apply Theorem 2.12 to obtain a subset P ⊂ Gn+1 of size |Y1 |2 , and λ (Gn+1 , P) < 1/1000 +
1/50. Define Yn+1 to be the set of all words of length 2 in P. This is a set of size |Y1 |4 and (by
Observation 2.10) λ (Gn+1 ,Yn+1 ) < (1/1000 + 1/50)2 < 1/1000. This completes the inductive step.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 101
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
5 Proof of Theorem 4.6
The theorem appears in Section 4. Let G,Y, X, λ be as defined in Theorem 4.6. We will use the notation
W = W (G) and W (Gd ),Wb̄ defined in Section 2.2.1. We need to prove that for every w ∈ W (Gd )⊥ such
that kwk = 1, at least one of the following upper bounds holds:
7
k E [Px (w)]k ≤ 0.01 + λ + , or (5.1)
x∈X (d) c
6
k E [Px (w)]k ≤ 0.01 + e−kc(1−λ )/10 . (5.2)
x∈X (d)
We saw in Section 2.2.1 that it is enough to prove this for w ∈ Wb̄ when b̄ 6= {||}d . Since X (d) is invariant
⊗(d−r)
under permutation of the coordinates it is enough to prove the inequality for every w ∈ W⊥⊗r ⊗W||
where 1 ≤ r ≤ d (this is Wb̄ for bi =⊥ for 1 ≤ i ≤ r and bi = || for r < i ≤ d).
We split the proof to small and large r cases. For small r we will prove inequality (5.1), and for large
r we will prove inequality (5.2). p
Small r case: When r ≤ 0.1 d/|X|, the first r coordinates of a random element in X (d) are very
closely a random element in X r . By Observation 2.8 Px (w) only depends on the first r coordinates of
x, so it is enough to bound k Ex∈X r [Px (w)]k for w ∈ W⊥⊗r . By Claim 2.2 k Ex∈X r [Px (w)]k ≤ λ (G, X)r .
The worst case is when r = 1. As Y ⊂ X we can use Claim 2.4 to give an upper bound to λ (G, X),
and we obtain inequality (5.1). This part is relatively easy, and we will not give a more detailed proof.
Notice however that the argument for small r works for any group G, not only for our special sequence
of groups, and from the generating set X we only used the Y part - not the Y ∗ part.
Large r case: When r is large the result is no longer true for any group (for any Abelian group there
exists an f ∈ W ⊗d such that Py ( f ) = f for all y ∈ Y (d) ). We will need the Y ∗ part of the generating
set X (recall that it is only defined when every element of G is a commutator). We will start with the
analysis of a different graph - the Cayley graph C(G × G, {(y, y−1 )|y ∈ Y ∗ }). We give a lower bound of
(1 − λ (G,Y ))/21|Y ∗ |2 on the spectral gap of this graph in Section 5.1. Afterward, in Section 5.2, we
will give an upper bound on k Ex∈X (d) [Px (w)]k using the spectral gap of this graph on G × G. This part is
again true for every group G, not only our groups.
Notice that the spectral gap bound we get in the G × G case is rather weak - much smaller than
the spectral gap of the original graph C(G,Y ). When r is large enough we are able to apply the G × G
result many times in parallel, amplifying the weaker upper bound in G × G. We will obtain the upper
bound (5.2).
5.1 Expansion of G × G with correlated generators
Definition 5.1. Let G be a group, and let Y ⊂ G be a subset of G. Define
Ye = {(y, y−1 ) | y ∈ Y } .
Theorem 5.2. Suppose λ (G,Y ) < 1 − ε for some ε, and that every element of Y is a commutator in G.
Then
ε
λ (G × G, Yf∗ ) ≤ 1 − .
21|Y ∗ |2
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 102
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
We find Theorem 5.2 quite surprising. In the set Ye there is complete correlation between the two
coordinates, and it would seem that this correlation would prevent the graph from being an expander.
For example, if G is Abelian and Y generates G then Ye does not even generate G × G, but only the
subgroup {(g, g−1 ) | g ∈ G}. Also, for any group G the set {(y, y) | y ∈ Y } only generates the subgroup
{(g, g) | g ∈ G}. In both cases the correlation in the generating set prevents the graph from being an
expander. We manage to decouple this correlation in the case of the special generating set Y ∗ , whose
existence relies on the commutator property of G.
The key observation is that we can represent the element (y, 1) for any y ∈ Y as a word of length 3
in Y ∗ . We prove this in the following observation.
f
Observation 5.3. Let Z be the set of words of length 3 in the set Yf∗ . Then
C(G × G, {(Y, 1) ∪ (1,Y )}) ⊂ C(G × G, Z) .
Proof. Recall that for every y ∈ Y the set Y ∗ contains the elements ay , by , a−1 −1 −1 −1
y by where y = ay by ay by .
Observe that
(ay , a−1 −1 −1 −1 −1 −1 −1
y ) · (by , by ) · ((ay by ), (ay by ) ) = (y, 1) .
This gives the required representation of (y, 1). We can obtain (1, y) similarly.
It is easy to see that if C(G,Y ) has spectral gap ε then the graph C(G × G, {(Y, 1) ∪ (1,Y )}) has
spectral gap ε/2. We now have the decoupling we were looking for - the correlated generating set Z
contains the uncorrelated one (Y, 1) ∪ (1,Y ). More precisely, apply Claim 2.4 to observation 5.3, and
deduce that
Observation 5.4. C(G × G, Z) has spectral gap at least ε/7|Y ∗ |2 .
Recall that Z consists of all words of length 3 in the Yf∗ . By Observation 2.10, the spectral gap of
C(G × G, Yf∗ ) is at most 3 times smaller than the spectral gap of C(G × G, Z), and the theorem is proved.
5.2 Reduction to G × G
We bound the average k Ex∈X (d) [Px (w)]k from above in terms of λ (G × G, Yf∗ ) from Section 5.1.
For x ∈ X d write x = (x1 , x2 , x̄) where x1 , x2 ∈ G and x̄ ∈ Gd−2 . By the triangle inequality,
Claim 5.5. For every w ∈ W ⊗d
k E [Px (w)]k ≤ E k(Px1 ,x2 ,x̄ + Px2 ,x1 ,x̄ )(w)/2k .
x∈X (d) x∈X (d)
By Observation 2.9 the value of k(Px1 ,x2 ,x̄ + Px2 ,x1 ,x̄ )(w)/2k only depends on the first two coordinates
of x. We therefore group together all the x with equal x1 , x2 , replacing x̄ by 1̄, a (d − 2)-length vector
of 1’s, and it is enough to bound Ex∈X (d) k(Px1 ,x2 ,1̄ + Px2 ,x1 ,1̄ )(w)/2k. The number of times each pair
x1 , x2 appears in the average above is proportional to the number of extensions of x1 , x2 to a vector
(x1 , x2 , x̄) ∈ X (d) . As d is much larger than 2, the number of such extensions is nearly equal for every
pair x1 , x2 , and we obtain the following:
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 103
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
Claim 5.6. If d ≥ 100|X| then for every w ∈ W ⊗d
E k(Px1 ,x2 ,x̄ + Px2 ,x1 ,x̄ )(w)/2k ≤ E k(Py1 ,y2 ,1̄ + Py2 ,y1 ,1̄ )(w)/2k + 0.01kwk .
x∈X (d) y∈X 2
The 0.01 above pays for the fact that the number of extensions is only nearly equal.
The following lemma bounds the RHS of Claim 5.6.
Lemma 5.7. If λ (G,Y ) < 1 − ε and r ≥ 2 then for every w ∈ W⊥⊗r ⊗W ⊗(d−r)
cε def
E k(Py1 ,y2 ,1̄ + Py2 ,y1 ,1̄ )(w)/2k ≤ (1 − )kwk = ∆kwk .
y∈X 2 2 · 104 |X|3
We prove the lemma in Section 5.2.1.
Combining Claim 5.6 and Lemma 5.7 we obtain
E [Px (w)] ≤ (∆ + 0.01)kwk
x∈X (d)
but ∆ is too close to 1. The problem originates from Claim 5.5, where we partitioned the set X (d) into
pairs based on the value of the first 2 coordinates. This partition turns out to be too coarse. We will use a
finer partition of X (d) by looking at the first t pairs of coordinates, for some properly chosen t ≤ r. This
will amplify the bound to ∆t .
We now define this finer partition precisely. Let Ht < Sd be the subgroup (of size 2t ) generated by
the transpositions (2k − 1, 2k) for 1 ≤ k ≤ t, and group together the elements {σ (x) | σ ∈ Ht }. When
t = 1 we get the grouping into pairs discussed above. The argument leading to Claim 5.6 shows the
following:
Claim 5.8. If 2t ≤ 0.1 d/|X| then for every w ∈ W ⊗d
p
h i
E [Px (w)] ≤ E E Pσ (y,1̄) (w) + 0.01 .
x∈X (d) y∈X 2t σ ∈Ht
The case t = 1 is Claim 5.6. However, the weak upper bound ∆ we had for t = 1 amplifies to ∆t .
Claim 5.9. Suppose that for every w ∈ W⊥⊗2 ⊗W ⊗d−2
1
E (P + Py2 ,y1 ,1̄ )(w) ≤ ∆kwk .
y∈X 2 2 y1 ,y2 ,1̄
Then for every w ∈ W⊥⊗2t ⊗W ⊗d−2t
h i
E E Pσ (y,1̄) (w) ≤ ∆t kwk .
y∈X 2t σ ∈Ht
The notation 1̄ denotes a vector of length d − 2 in the first inequality, and a vector of length d − 2t in the
second one.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 104
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
Proof. The proof is by induction on t. The case t = 1 is the assumption of the claim. For general t
h i
E E Pσ (y,1̄) (w) = E E Pσ (1,1,y,1̄) Pz1 ,z2 ,1̄ + Pz2 ,z1 ,1̄ (w)
y∈X 2t σ ∈Ht z∈X 2 σ ∈Ht−1
y∈X 2(t−1)
≤ ∆t−1 E (Pz1 ,z2 ,1̄ + Pz2 ,z1 ,1̄ )(w) ≤ ∆t kwk .
z∈X 2
Note that in the second line above σ ∈ Ht−1 acts on the vector y - not on the first 2t − 2 coordinates. The
first inequality follows from the induction hypothesis for Ht−1 . The second inequality follows from the
induction hypothesis for H1 .
We can now complete the proof using λ (G,Y ) < 1 − ε. Pick an integer t satisfying
p p
0.05 d/|X| ≤ 2t ≤ 0.1 d/|X| ≤ r .
Then by the claims in this section, for w ∈ W⊥⊗r ⊗W ⊗d−r of norm 1,
cε t −ctε −kcε
E [Px (w)] ≤ 0.01 + 1 − 4 3
≤ 0.01 + exp 4 3
≤ 0.01 + exp .
x∈X (d) 2 · 10 |X| 2 · 10 |X| 106
p
We plugged in 2t ≥ 0.05 d/|X| ≥ 0.05k|X|3 . This concludes the proof of Theorem 4.6 for large r.
5.2.1 Proof of Lemma 5.7
Let τ be the spectral gap of C(G × G, {(y, y−1 ) | y ∈ Y ∗ }). From Theorem 5.2 we have for every u ∈
W⊥ ⊗W
E ∗ Py,y−1 (u) ≤ (1 − τ)kuk . (5.3)
y∈Y
In Lemma 5.7 we want to bound
E k(Py1 ,y2 ,1̄ + Py2 ,y1 ,1̄ )(w)/2k (5.4)
y∈X 2
from above, for every w ∈ W⊥⊗r ⊗W ⊗(d−r) .
We will start with the case d = 2. We will bound (5.4) in terms of the LHS of (5.3). In order to do
that, we will have to deal with the fact that the norm in (5.3) appears outside the expectation, while in
(5.4) it appears inside the expectation (see Claim 5.10). Also, the average in (5.4) is over y ∈ X 2 , while
in (5.3) the average is over y ∈ Y ∗ (see Claim 5.11). After completing the proof in the case d = 2, we
turn to prove the lemma for general d (Claim 5.12).
Claim 5.10. For every u ∈ W⊥ ⊗W
1
E (Py,1 + P1,y )(u) ≤ (1 − τ/4)kuk .
y∈Y ∗ 2
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 105
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
Proof. From Claim 2.5 and (5.3)
1
E (P −1 + I)(u) ≤ (1 − τ/4)kuk .
y∈Y ∗ 2 y,y
Applying the unitary operator P1,y to each element above proves the claim.
Claim 5.11. For every u ∈ W⊥ ⊗W
1 τ
E (Py1 ,y2 + Py2 ,y1 )(u) ≤ (1 − )kuk .
y∈X 2 2 8c|X|
Proof. Let p be the probability that for a random y ∈ X 2 we have y1 ∈ Y ∗ and y2 = 1. Then p ≥
(1/2c)·1/|X| (as X = c·Y ∪Y ∗ and Y ∗ is larger than Y ). Using a convexity argument similar to Claim 2.4
we see that
1 1
E (Py1 ,y2 + Py2 ,y1 )(u) ≤ p · E ∗ (Py,1 + P1,y )(u) + (1 − p) · kuk
y∈X 2 2 y∈Y 2
τ
≤ p · (1 − τ/4)kuk + (1 − p)kuk ≤ (1 − pτ)kuk ≤ (1 − )kuk
8c|X|
which proves Claim 5.11.
We have shown that for every u ∈ W⊥ ⊗W
1 τ ε cε
E (Py1 ,y2 + Py2 ,y1 )(u) ≤ 1 − kuk ≤ 1 − ∗ 2
kuk ≤ 1 − 4 3
kuk .
y∈X 2 2 8c|X| 21 · 8|Y | · |X| 2 · 10 |X|
The last step follows from |Y ∗ | ≤ 10|X|/c (which is true since X = cY ∪Y ∗ and |Y ∗ | ≤ 10|Y |).
We have almost completed proving the lemma. We have the right upper bound, but for u ∈ W ⊗2
instead of in W ⊗d .
Claim 5.12. If there exists λ > 0 such that for every u ∈ W⊥⊗2
1
E [ (Py1 ,y2 + Py2 ,y1 )(u)] ≤ λ kuk
y∈X 2 2
then for every w ∈ W⊥⊗2 ⊗W ⊗(d−2)
1
E [ (Py1 ,y2 ,1̄ + Py2 ,y1 ,1̄ )(w)] ≤ λ kwk .
y∈X 2 2
Proof. Write w ∈ W⊥⊗r ⊗W ⊗(d−r) as w = ∑ ui ⊗ vi where ui ∈ W⊥⊗2 and vi ∈ W ⊗(d−2) , such that the vi are
orthogonal and kvi k = 1. We have
2 2
1 1
E [ (Py1 ,y2 ,1̄ + Py2 ,y1 ,1̄ )(w)] = E ∑ [ (Py1 ,y2 + Py2 ,y1 )(ui )] ≤ λ 2 kwk2
y 2 y
i 2
and the result follows since E(X)2 ≤ E(X 2 ) for any random variable X.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 106
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
6 Proof of Theorem 2.14
The theorem appears in Section 2.2.3.
Remark 6.1. This section contains equations in groups. Constants in the equations will be written in
Greek letters. Variables will be written in small Latin letters. Vectors of length d are underlined.
Let C = A o B, where A is any group and B ⊂ Sd . Given an element γ ∈ C we look for a “commutator
representation algorithm” that solves the equation γ = [c1 , c2 ] := c1 c2 c1 −1 c2 −1 . By assumption we have
such an algorithm for A and B. The proof below extends Nikolov’s proof in [37].
Any element γ ∈ A o B has a unique representation c = β · α with β ∈ B, α ∈ Ad , so it is enough to
solve, for every pair (β ∈ B, α ∈ Ad ), the equation β α = [b1 x, b2 y]. Now
−1 −1 −1 −1 −1 −1 −1
[b1 x, b2 y] = [b1 , b2 ] · xb2 b1 b2 yb1 b2 x−b1 b2 y−b2
where xb = b−1 xb. In our case xb is simply a permutation of the coordinates of x by b ∈ B ⊂ Sd .
We obtain a pair of equations:
β = [b1 , b2 ], and
−1 −1 −1 −1 −1 −1 −1
α = xb2 b1 b2 yb1 b2 x−b1 b2 y−b2 .
By assumption there is an algorithm that solves β = [b1 , b2 ]. Fix some solution b1 = β1 , b2 = β2 . It
remains to solve
−1 −1 −1 −1 −1 −1 −1
α = xβ2 β1 β2 yβ1 β2 x−β1 β2 y−β2 .
Since xβ is a permutation (depending on β ) of the coordinates of x, the following lemma solves a more
general system of equations.
Lemma 6.2. For any four permutations σ1 , σ2 , σ3 , σ4 ∈ Sd and for any α = α1 , . . . , αd ∈ Ad , the follow-
ing system of d equations, one for each 1 ≤ i ≤ d:
αi = xσ1 (i) yσ2 (i) xσ−13 (i) y−1
σ4 (i)
has a solution algorithm that calls the commutator representation algorithm on A at most d times, and
does at most O(d) operations in the group A.
The rest of this section is devoted to the proof of this lemma.
Definition 6.3. We shall refer to the αi as constants and to the xi , yi , xi−1 , y−1
i as literals.
There are d constants and 4d literals in our system. An important fact is that each literal appears
exactly once in the system.
Let us solve first in the case that all four σi are the identity permutation. The system in this case is:
α1 = [x1 , y1 ]
α2 = [x2 , y2 ]
···
αd = [xd , yd ]
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 107
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
In this case the equations are independent (no variable appears in more than one equation). Each equation
asks for a commutator representation for αi ∈ A. We solve the system of equations by calling the
commutator representation algorithm for A for each equation separately.
The solution for general σi is by reduction to a system similar to the one we obtained for the σi = 1
case. As long as there are variables that appear in more than one equation, we will remove equations by
“Gaussian elimination,” until we obtain a system of independent equations. We will then translate each
equation to a commutator representation equation like the ones above.
As mentioned, each literal appears exactly once in the system. If xi , xi−1 do not both appear in the
same equation, then we can eliminate xi , xi−1 from the system by substitution (paying O(1) multiplica-
tions in A). This reduces the number of equations in the system by 1. Repeat the substitution operation
until it is no longer possible. Notice that the property that each literal appears exactly once is preserved
along the way.
Claim 6.4. The substitution process ends with L ≤ d equations
δl = Wl ∀l ∈ {1, . . . , L}
where Wl is some word in literals and constants. The equations are now independent - every literal
appears in the same equation as its inverse, or they both do not appear in the system.
We will now reduce this system to L commutator representation problems in the group A. The
following lemma finds a “hidden commutator” in each of the words Wl :
Lemma 6.5. [37] In every Wl there exist g, h ∈ {1, 2, . . . , d} depending on l, such that
Wl = Z1 xg Z2 yh Z3 xg−1 Z4 y−1
h Z5
where the Zi are words in literals and constants from the word Wl (they do not contain xg±1 , xh±1 since
each literal appears at most once in the system of equations).
The proof is in [37]. Given that such a hidden commutator exists, it is easy to find one in time
polynomial in d by looking at all the literals appearing in Wl (there are at most 2d of those). Substitute
every variable appearing in the Zi by 1. This does not affect any other equation - the equations are
independent at this point. We obtain a new equation
δl = ζ1 xg ζ2 yh ζ3 xg−1 ζ4 y−1
h ζ5 .
This is now an equation in two variables xg , xh - all the other words are constants. This is almost a
“commutator representation” equation. Indeed, if the five ζi are all equal 1, we obtain the equation
δl = [xg , yh ]
which is solved by calling the commutator algorithm on A. For general ζi we transform the “hidden”
commutator to a “real” commutator by changing variables. Define x̃g = ζ3 xg ζ4 and ζh = yh ζ2−1 ζ3−1 .
Observe that
δl = ζ1 ζ4 [x̃g , ỹh ]ζ3 ζ2 ζ5 .
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 108
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
Rewrite this equation as
(ζ1 ζ4 )−1 δl (ζ3 ζ2 ζ5 )−1 = [x̃g , ỹh ] .
The LHS is some constant element in A, and the equation requests a representation of this element as
a commutator. We can find a solution by calling the commutator representation algorithm on A. The
solution is in the variables x̃g , ỹh , but this is easily translated to a solution in our original variables xg , yh .
How many operations did we use? We called the commutator representation algorithm in A at most
d times (one call for each final equation vl = Wl ). We called the commutator representation algorithm
on B one time. We used O(1) multiplications in B, and O(d) multiplications in A (there were O(1) per
either removing an equation or solving a final equation).
We can now deduce Lemma 3.2. Define m(n) to be the cost (in bit operations) of multiplication in
Gn , and define c(n) to be the cost of computing the commutator representation of an element in Gn . As
m(n+1) < (d +1)m(n) and m(1) = O(d 2 ) we deduce that m(n) < (d +1)n+2 ·O(1). From the discussion
above we see that c(n + 1) < (d + 1)c(n) + m(n) · O(d) < (d + 1)c(n) + d n+3 · O(1). This implies that
c(n) < d 4n · O(1) for large enough d. Finally, as log |Gn | > d n , Lemma 3.2 follows.
7 Expanding Schreier graphs
For a finite group H, a subgroup H 0 < H, and a (symmetric) set of elements U in it, the Schreier graph
Sch(H, H 0 ,U) has vertex set H/H 0 , and edges (gH 0 , ugH 0 ) for every u ∈ U, resulting in a |U|-regular
graph. If H 0 = {1} then Sch(H, {1},U) is simply the Cayley graph C(H,U).
In this section we prove an analogue of Theorem 4.1 for Schreier graphs. In Theorem 4.1 we con-
structed a sequence of expanding Cayley graphs assuming the existence of a good “seed” Cayley graph.
Here we do the same for Schreier graphs. The difference here is that the “seed” Schreier graph is known
to exist by elementary arguments, and we do not rely on the strong theorem of [22]. By [17], every
2d-regular graph is a Schreier graph, so a sequence of expanding Schreier graphs is implicit in any se-
quence of (even degree regular) expander graphs. However, it is generally hard to compute a Schreier
graph representation of a given d-regular graph. In this section we explicitly provide the Schreier graph
representation of our graphs.
There is another way to describe Schreier graphs. Let H be a group acting transitively on a set E.
Define a graph Sch(H, E,U) whose vertices are E, and whose edges are (e, ue) for all u ∈ U and e ∈ E.
Pick a vertex e0 ∈ E, and define H 0 = {h ∈ H | he0 = e0 ), the stabilizer of e0 . The graph we defined on
E is isomorphic to Sch(H, H 0 ,U) by taking he0 to hH 0 . The following definition gives an example of
groups acting on sets. This example will be the basis of a construction of expander Schreier graphs. To
fix notation, we redefine our basic objects:
Definition 7.1. Let Tn,d be the rooted d-regular tree with depth n, let Sym(n, d) be its group of symme-
tries, and let En be the set of leaves of Tn,d , on which Sym(n, d) acts naturally.
Expansion of a Cayley graph implies the expansion of all its Schreier graphs:
Claim 7.2. Let H be a group , let H 0 < H be a subgroup and let U ⊂ G be a subset. Then λ (Sch(H, H 0 ,U)) ≤
λ (C(H,U)).
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 109
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
Proof. Let v : H/H 0 → C be an eigenvector of the Schreier graph. Define v̂ : H → C by v̂(h) = v(hH 0 ).
Then v̂ is an eigenvector of C(H,U) with the same eigenvalue as v.
In Theorem 4.1 we constructed a sequence of Cayley graphs C(Gn ,Yn ) where Gn is a subgroup of
Sym(n, d), and showed that it is an expander family under some assumption on the symmetric group
Ad , which is true for very large d. In light of Claim 7.2, the family Sch(Gn , En ,Yn ) is also a sequence
of expander graphs, under the same assumption. Below we construct expanding generating sets for Gn ,
which are both simpler than Yn and do not require any assumptions (and work for much smaller d).
Reminder: for two groups G, K, such that K < Sd , the wreath product G o K has elements Gd × K and
multiplication rule
(g1 , . . . , gd , σ ) · (g̃1 , . . . , g̃d , τ) = (gτ(1) g̃1 , . . . , gτ(d) g̃d , σ τ) .
Elements of Gd are naturally embedded in G o K by setting the K coordinate to be 1. The group K is
embedded in G o K similarly by setting the Gd coordinates to be 1.
Definition 7.3. Given a group K < Sd , define a sequence of groups inductively by K1 = K and Kn+1 =
Kn o K (The groups Gn of Theorem 4.1 are such groups with K = Ad ). Recall that each element in
Sym(n, d) is uniquely defined by writing a permutation in Sd on each internal node of Tn,d , indicating
how the children of this vertex are permuted. The group Kn is the subgroup of Sym(n, d) where the
permutation written on every internal vertex is an element of K. The group Kn acts on the set En (the
leaves of the d-regular depth n tree) via its embedding in Sym(n, d).
The following theorem is the Schreier graph analogue of Theorem 4.1.
Theorem 7.4. If there is a generating set Q ⊂ K of size at most (d 1/4 /2) with λ (K, [d], Q) ≤ 1/4,
then there exist Qn ⊂ Kn of size |Q|4 such that λ (Kn , En , Qn ) ≤ 1/4, and Qn can be computed in time
polynomial in log |En |.
The main difference from Theorem 4.1 is that in the Schreier case the set Q is known to exist for
many groups K. The claim below shows the existence of such Q for K = Sd (for d large enough).
Claim 7.5. Let d ≥ 100, and let U be 100 permutations in Sd chosen randomly uniformly. Then
λ (Sd , [d],U) ≤ 1/4 with probability larger than 1/2.
For proofs see [13] (or [9] for a weaker result which would result in a larger required d).
Corollary 7.6. For every d ≥ 4 · 1004 there is a sequence of subsets Un ⊂ Sym(n, d) of size 1004 such
that λ (Sym(n, d), En ,Un ) < 1/4. Furthermore, Un is computable in time polynomial in log |En |.
Proof of Theorem 7.4: We will assume that |Q|4 divides d. The divisibility condition is not crucial,
but it simplifies the proof. We proceed by induction - the case n = 1 is the assumption of the theorem.
Assume the theorem holds for some n. We show that it holds for n + 1.
(d)
Claim 7.7. Let Qn be the vectors in Qdn in which every element in Qn appears exactly d/|Qn | times (see
(d)
Definition 4.4). Let x = (x1 , . . . , xd ) be an element of Qn . Define U = {yxz | y, z ∈ Q} ⊂ Kn+1 . Then
λ (Kn+1 , En+1 ,U) ≤ λ (Kn , En , Qn ) + λ (K, [d], Q).
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 110
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
We prove the claim later, and now proceed with the proof of the theorem. Define Qn+1 to be the set
of words of length 2 in the set U given by Claim 7.7. Then
2
λ (Kn+1 , En+1 , Qn+1 ) = λ (Kn+1 , En+1 ,U)2 ≤ λ (Kn , En , Qn ) + λ (K, [d], Q)) ≤ (1/4 + 1/4)2 ≤ 1/4
where the equality follows from Observation 2.3, the first inequality is Claim 7.7 and the second in-
equality is the induction assumption. By definition |Qn+1 | = |Q|4 . This concludes the proof of Theo-
rem 7.4
Proof of Claim 7.7. The proof uses the zig-zag theorem [42]. Here is a quick definition of the zig-zag
product:
Definition 7.8. Let X, Y be regular graphs such that the degree of X is equal the size of Y. For every
v ∈ X write the list of neighbors of v as an array v[i] for i ∈ Y (the ordering of the list of neighbors is
arbitrary, and different lists may lead to different graphs). Define a graph Z whose vertices are pairs
(v, i), with v ∈ X and i ∈ Y. The neighbors of a vertex (v, i) are the vertices reached by making the
following three steps:
• Step 1: Walk from (v, i) to (v, j) where (i, j) is an edge of Y.
• Step 2: Walk from (v, j) to (v[ j], j) where v[ j] is the j-th neighbor of v in the graph X.
• Step 3: Walk from (v[ j], j) to (v[ j], k) where ( j, k) is an edge of Y.
Z has degree (deg Y)2 . It is called the zig-zag product of X and Y, and we write Z = X z Y.
Theorem 7.9 ([42]). If Z = X z Y then λ (Z) ≤ λ (X) + λ (Y).
Define Q fn to be the multiset of size d obtained by duplicating every element of Qn exactly d/|Qn |
times. Notice that the vector x is simply a list of the elements of Q fn . Let X = Sch(Kn , En , Q fn ), Y =
Sch(K, [d], Q), and Z = Sch(Kn+1 , En+1 ,U). We claim that Z = X z Y. The proof of Claim 7.7 then
follows from Theorem 7.9 (notice that λ (X) = λ (Kn , En , Qn )). The first requirement is that the degree
of X is equal to the size of Y, and indeed they are both d. It remains to verify that edges of Z are the
walks of length 3 of the zig-zag product. For every v ∈ X and i ∈ Y define v[i] = xi (v) (the element
xi ∈ Kn acts on v ∈ En ). The array v[i] is the list of neighbors of v in X. An edge of Z connects (v, i) to
yxz(v, i) (embedded in Kn+1 as y = (1, 1, . . . , 1, y), z = (1, 1, . . . , 1, z) and x = (x1 , x2 , . . . , xd , 1)). Let (v, i)
be a vertex of Z, and let j = z(i), and k = z( j) = yz(i). Then
yxz(v, i) = yx(v, z(i)) = yx(v, j) = y(x j (v), z(i)) = y(v[ j], j) = (v[ j], k) .
This is exactly the definition of an edge in the zig-zag product, and we have proved Claim 7.7.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 111
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
8 Generators for an infinite group with property (τ)
There are natural mappings, for k ≤ n between Sym(n, d) and Sym(k, d). The embedding map sends an
element σ ∈ Sym(k, d) to the element of Sym(n, d) which acts on the first k levels of the tree by σ . The
restriction map sends τ ∈ Sym(n, d) to its restriction to the first k levels of the tree.
In Theorem 4.1 we constructed subsets Yn ⊂ Gn < Sym(n, d) that generated Gn as expanders. In this
section we will prove that the sets Yn are consistent: the restriction of Yn to Sym(k, d) is exactly Yk . This
implies that there is a set Y∞ of symmetries of the infinite rooted d-regular tree, which restricts to Yn for
any n. A nice corollary is that the infinite group generated by Y∞ has property τ (defined below) with
respect to some sequence of subgroups. In the next section we will use this consistency to construct a
sequence of expander graphs each of which is a lift of its predecessor.
Theorem 8.1. Let Yn ⊂ Gn be the groups and generating (multi)sets of Theorem 4.1. Then for every
n ≥ k ≥ 2 the restriction of Yn to Sym(k, d) is equal Yk . The same holds for the sets Qn of Theorem 7.4.
Corollary 8.2. Define Y∞ to be the set of symmetries of the infinite tree whose restriction to Sym(n, d) is
Yn . The set Y∞ generates an infinite subgroup G∞ of the symmetries of the infinite tree, and the restriction
of G∞ to Sym(n, d) is Gn for all n ≥ 2. The same holds for Qn of Theorem 7.4.
The following definition of property (τ) is from [30], page 49.
Definition 8.3. Let G be a finitely generated group, and let Y be a finite symmetric generating set for
G. Let L = {Nn }n∈N be a family of finite index normal subgroups in G. Then G has property (τ) with
respect to L if the family C(G/Nn ,Y /Nn ) is an expander family.
Corollary 8.4. Let Nn be the kernel of the restriction function from G∞ to Gn . Then, under the assump-
tion on the alternating group described in Theorem 4.1, the group G∞ has property (τ) with respect to
the family {Nn }∞
n=2 .
Proof of Theorem 8.1. The proof will only deal with the (harder) case of Yn . Recall that elements in
Sym(n, d) are represented by writing a permutation on each internal vertex of Tn,d . Define the k-th level
of an element u ∈ Sym(n, d) to be the permutations written on the k-th level of Tn,d in this representation
of u.
The following claim is somewhat complicated to state, but its proof is an easy induction.
Claim 8.5. Let Fi, j be sequence of functions Fi, j : Sym(∞, d)q → Sd , where 1 ≤ i ≤ q and j is an internal
vertex of T∞,d . Suppose that for vertices j in the k-th level of T∞,d , the output of Fi, j only depends on
levels 1 up to (k − 1) of its inputs (in particular Fi,1 is a constant function). Define U1 ⊂ Sym(n, d)
to be the set Fi,1 () for 1 ≤ i ≤ q, and inductively, given the set Un = un1 , un2 , . . . , unq in Sym(n, d) define
uin+1 ∈ Sym(n + 1, d) by writing the permutation Fi, j (un1 , un2 , . . . , unq ) in internal vertex number j of Tn+1,d .
Then the restriction of un+1
i to Sym(n, d) is uni .
Theorem 8.1 now follows by observing that the sets Yn are indeed constructed by the procedure in
Claim 8.5. (The only exception is Y1 which was constructed differently, so the theorem’s statement holds
only for n ≥ 2). To show this, recall briefly how we constructed Yn+1 given the set Yn .
• Construct the set Yn ∗ defined in Definition 4.5.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 112
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
• Write X = c ·Yn ∪Yn ∗ .
• Pick an element x ∈ X (d) ⊂ Sym(n, d)d , and embed it in Sym(n + 1, d).
• Define Z = Y1 xY1 by regarding the elements of Y1 as elements in Sym(n + 1, d).
• Define Yn+1 to be the set of words of length 2 in the set Z.
We will now verify that the (k + 1)-level an element in Yn+1 is a function of levels 1 up to k of the
elements in Yn . We will also verify that the first level of elements in Yn+1 is indeed a constant independent
of n. We leave to the reader to verify that the conditions of Claim 8.5 hold precisely, which we feel is
rather too technical.
Observation 8.6. Let g be an element of Gn . Let g = [x, y] be the commutator representation derived in
Section 6. Then level k of x and y depends only on levels 1 up to k of g.
The observation follows by following the construction of the commutator representation, which is
simply induction on the level. We conclude that for elements in Yn ∗ , and therefore in X, the k-th level
depends only on levels 1 up to k of the elements in Yn .
Observation 8.7. Let g, h be elements in Sym(∞, d). Then level k of gh depends only on levels 1 up to
k of g and h.
Observation 8.8. Let x = (x1 , . . . , xd ) be an element of Sym(n, d)d . Embed x in Sym(n + 1, d) as
(x1 , . . . , xd , 1), represented by writing a permutation on every internal vertex of Tn+1,d . The permuta-
tion written on the root is the identity, and the permutations written on level k + 1 are permutations
written on level k of x1 , . . . , xd .
The two observations above imply that level k + 1 of elements in Z depend only on levels 1 up to k
of X. Also, level 1 of elements in Z is independent of n, since it depends on level 1 of elements in Y1 and
level 1 of x which is the identity permutation. The same holds for Yn+1 as elements there are products of
elements of Z (we use Observation 8.7 again). This concludes the proof of the theorem.
9 A sequence of expanding lifts of graphs
Definition 9.1. Given a graph X, on n vertices v1 , . . . , vn , a d-lift of X is a graph Y on nd vertices wi,k
where i ∈ [n], k ∈ [d]. For each edge e = (vi , v j ) of X choose a permutation σe ∈ Sd , and connect wi,k
with w j,σe (k) for all k ∈ [d]. The vertices wi,k for fixed i and k ∈ [d] are called the fiber above vi . The
fibers above an edge e = (vi , v j ) are connected by a perfect matching defined by σe . There are many
non-isomorphic lifts of a graph X depending on the choice of the permutations σe . For more information
on lifts see [6].
In this section we show how to obtain an explicit sequence of expander graphs, each of which is a
d-lift of its predecessor for any (large enough) d. Actually, the sequence of Schreier graphs constructed
in the previous sections do.
Here are some basic properties of lifts which are not hard to prove:
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 113
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
• The degree of a vertex v is equal to the degree of all the vertices in the fiber above v, so a lift of a
regular graph is regular with the same degree.
• The definition of a lift works fine for parallel edges and loops (where the loop counts as two edges
when computing the degree of a vertex).
• Lifting is transitive: If Y is a lift of X and Z is a lift of Y then Z is a lift of X.
• If Y is a lift of X then λ (Y) ≥ λ (X).
As an example, consider the graph X0 which consists of a single vertex with q loops on it. A lift
X1 of X0 is encoded by q permutations σ1 , . . . , σq ∈ Sd . The graph X1 has vertex set [d] and edges
(i, σl (i)), i ∈ [d], l ∈ [q], making it a 2q-regular graph.
Linial raised the following conjecture:
√(Linial). For every graph X and every d there exists a d-lift Y of X such that λ (Y) ≤
Conjecture 9.2
max(λ (X), O( d)).
For d = 2 a slightly weaker version of the conjecture was proved in [8].
The conjecture yields a method to construct a sequence of expander graphs each of which is a lift
of its predecessor. Pick any regular graph X1 with λ (X1 ) = 1/2. Now choose a sequence of graphs Xn
such that λ (Xn+1 ) ≤ λ (Xn ) and Xn+1 is a lift of Xn (we need the degree of the initial graph to be large
enough for this to work).
Theorem 9.3. Let Xn = Sch(Kn , En , Qn ) be the family of graphs of Theorem 7.4. Then Xn+1 is a d-lift
of Xn for all n ≥ 1.
By Corollary 7.6 we obtain the required sequence of expanding lifts:
Corollary 9.4. Let K = Sd with d ≥ 4 · 1004 , and let Q ⊂ Kn be the generating set given in 7.6. Let Xn
be the sequence constructed in Theorem 9.3. Then λ (Xn ) ≤ 1/4 for all n and Xn+1 is a d-lift of Xn for
all n ≥ 1.
The proof of Theorem 9.3 is by induction. The following two claims show how to construct a
Schreier graph of a wreath product G o H which is naturally a lift of a Schreier graph of H. These two
claims will be used in the induction step.
Claim 9.5. Let G, H be groups acting on EG , EH respectively. H is a subgroup of the symmetric group
on EH , so the group G o H is defined, and its elements are written as (g, h) where g = (gy )y∈EH and h ∈ H.
Then G o H acts on EG × EH by (g, h)(x, y) = (gy (x), h(y)).
Proof. We need to show that for two elements (g, h), (g̃, h̃) ∈ G o H and an element (x, y) ∈ EG × EH
(g, h) (g̃, h̃)(x, y)) = (g, h) · (g̃, h̃) (x, y) .
And indeed,
(g, h) (g̃, h̃)(x, y)) = (g, h)(g̃y (x), h̃(y)) = (gh̃(y) · g̃y , h · h̃)(x, y) = (g, h) · (g̃, h̃) (x, y) .
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 114
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
Claim 9.6. Let G, H be as in Claim 9.5, and let U be a subset of G o H. Then Sch(G o H, EG × EH ,U) is
a |EG |-lift of Sch(H, EH ,U). (Notice that we have identified U with its restriction to H).
Proof. The vertices of Sch(G o H, EG × EH ,U) are pairs (x, y) with x ∈ EG and y ∈ EH . Partition these
vertices to subsets Sy = {(x, y) | x ∈ EG }. We will show that Sch(G o H, EG × EH ,U) is a |EG |-lift of
Sch(H, EH ,U) where the fiber above y ∈ EH is Sy . In order to prove this, we need to show that for every
edge e = (y1 , y2 ) of Sch(H, EH ,U) there corresponds a perfect matching between Sy1 and Sy2 .
Edges in Sch(H, EH ,U) are of the form (y, uy), for y ∈ EH and u ∈ U. Write u = (g, h) in G o H, so
uy = h(y). In Sch(G o H, EG × EH ,U), a vertex (x, y) is connected to u(x, y) = (gy (x), h(y)). This is a
perfect matching between Sy and Sh(y) since gy is a permutation of EG for y fixed.
Can we use Claim 9.6 to obtain a sequence of expanding lifts? In Section 8 we constructed an
expander sequence Xn = Sch(Kn , Qn , En ) where each Qn is the restriction of a single set Q∞ . Since
Kn+1 = Kn o K we deduce by Claim 9.6 that Sch(Kn+1 , Q∞ , En+1 ) is a lift of Sch(K, Q∞ , [d]) = X1 , while
we wanted Xn+1 to be a lift of Xn . The following observation comes to the rescue (notice the change of
order in the wreath product).
Observation 9.7. Let Kn be the sequence of groups defined in 7.3. Consider Kn as a subset of the
permutation group on En . Then Kn+1 = K o Kn .
We can now use Claim 9.6 to conclude that Sch(Kn+1 , Q∞ ) is a d-lift of Sch(Kn , Q∞ ), which proves
Theorem 9.3.
Acknowledgments
We are grateful to Alex Lubotzky for many insightful conversations, in part supplying the group theoretic
tools we ended up needing for the proof. We thank Yair Glasner and Shachar Mozes for useful remarks.
We thank the anonymous referee for many helpful comments.
References
[1] * M IKL ÓS A JTAI , J ÁNOS KOML ÓS , AND E NDRE S ZEMER ÉDI: Sorting in c log n parallel steps.
Combinatorica, 3(1):1–19, 1983. 1.1
[2] * N OGA A LON: Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. 1.1
[3] * N OGA A LON , Z VI G ALIL , AND V ITALI D. M ILMAN: Better expanders and superconcentrators.
Journal of Algorithms, 8(3):337–347, 1987. [JAlg:10.1016/0196-6774(87)90014-9]. 1.1
[4] * N OGA A LON , A LEXANDER L UBOTZKY, AND AVI W IGDERSON: Semi-direct product in groups
and zig-zag product in graphs: connections and applications (extended abstract). In Proc. of the
42nd Annual Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pp. 630–637.
IEEE Computer Soc., Los Alamitos, CA, 2001. [FOCS:10.1109/SFCS.2001.959939]. 1.2, 1.3,
2.2.2, 2.12
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 115
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
[5] * N OGA A LON AND V ITALI D. M ILMAN: λ1 , isoperimetric inequalities for graphs,
and superconcentrators. Journal of Combinatorial Theory. Series B, 38(1):73–88, 1985.
[JCombThB:10.1016/0095-8956(85)90092-9]. 1.1
[6] * A LON A MIT AND NATHAN L INIAL: Random graph coverings. I. General theory and graph
connectivity. Combinatorica, 22(1):1–18, 2002. [Combinatorica:er6qljcyq3v8pyd2]. 9.1
[7] * E LI B EN -S ASSON , M ADHU S UDAN , S ALIL VADHAN , AND AVI W IGDERSON: Randomness-
efficient low degree tests and short PCPs via epsilon-biased sets. In Proc. of the 35th Annual ACM
Symposium on Theory of Computing, pp. 612–621. ACM Press, 2003. [STOC:780542.780631].
1.2
[8] * YONATAN B ILU AND NATI L INIAL: Constructing expander graphs by 2-lifts and discrepancy
vs. spectral gap. In Proc. of the 45th Annual Symposium on Foundations of Computer Science, pp.
404–412, Rome, Italy, 17-19 October 2004. IEEE. [FOCS:10.1109/FOCS.2004.19]. 9
[9] * A NDREI B RODER AND E LI S HAMIR: On the second eigenvalue of random regular graphs (pre-
liminary version). In Proc. of the 28th Annual Symposium on Foundations of Computer Science,
pp. 286–294, Los Angeles, California, 12–14 October 1987. IEEE. 7
[10] * M ICHAEL C APALBO , O MER R EINGOLD , S ALIL VADHAN , AND AVI W IGDERSON: Random-
ness conductors and constant-degree lossless expanders. In Proc. of the 34th Annual ACM Sympo-
sium on Theory of Computing, pp. 659–668. ACM Press, 2002. [STOC:509907.510003]. 1.1
[11] * P ERSI D IACONIS AND M EHRDAD S HAHSHAHANI: On the eigenvalues of random matrices. J.
Appl. Probab., 31A:49–62, 1994. 1.2
[12] * M ARTIN E ICHLER: Quaternäre quadratische Formen und die Riemannsche Vermutung für die
Kongruenzzetafunktion. Arch. Math., 5:355–366, 1954. 1.2
[13] * J OEL F RIEDMAN: A proof of Alon’s second eigenvalue conjecture. Memoirs of the AMS, to
appear. [arXiv:cs.DM/0405020]. 7
[14] * O FER G ABBER AND Z VI G ALIL: Explicit constructions of linear-sized superconcentrators.
Journal of Computer and System Sciences, 22(3):407–420, June 1981. [JCSS:10.1016/0022-
0000(81)90040-4]. 1.1
[15] * O DED G OLDREICH , RUSSELL I MPAGLIAZZO , L EONID L EVIN , R AMARATHNAM V ENKATE -
SAN , AND DAVID Z UCKERMAN : Security preserving amplification of hardness. In Proc. of the
31st Annual Symposium on Foundations of Computer Science, volume I, pp. 318–326, St. Louis,
Missouri, 22–24 October 1990. IEEE. 1.1
[16] * M ISHA G ROMOV: Spaces and questions. Geometric and Functional Analysis, pp. 118–161,
2000. Part I of Special Volume on GAFA 2000 (Tel Aviv, 1999). 1.1
[17] * J ONATHAN L. G ROSS: Every connected regular graph of even degree is a Schreier coset graph.
Journal of Combinatorial Theory. Series B, 22(3):227–232, 1977. [JCombThB:10.1016/0095-
8956(77)90068-5]. 1.2, 7
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 116
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
[18] * RUSSELL I MPAGLIAZZO , N OAM N ISAN , AND AVI W IGDERSON: Pseudorandomness for net-
work algorithms. In Proc. of the 26th Annual ACM Symposium on the Theory of Computing, pp.
356–364, Montréal, Québec, Canada, 23–25 May 1994. [STOC:195058.195190]. 1.1
[19] * RUSSELL I MPAGLIAZZO AND AVI W IGDERSON: P = BPP if E requires exponential circuits:
Derandomizing the XOR lemma. In Proc. of the 29th Annual ACM Symposium on Theory of
Computing, pp. 220–229, El Paso, Texas, 4–6 May 1997. [STOC:258533.258590]. 1.1
[20] * S HUJI J IMBO AND A KIRA M ARUOKA: Expanders obtained from affine transformations. Com-
binatorica, 7(4):343–355, 1987. 1.1, 1.2
[21] * N IGEL J. K ALTON AND JAMES W. ROBERTS: Uniformly exhaustive submeasures and nearly
additive set functions. Transactions of the American Mathematical Society, 278(2):803–816, 1983.
1.1
[22] * M ARTIN K ASSABOV: Symmetric groups and expander graphs. arxiv:math.GR/0505624.
[arXiv:math.GR/0505624]. 1.1, 1.2, 4.2, 7
[23] * M ARTIN K ASSABOV: Universal lattices and unbounded rank expanders.
arxiv:math.GR/0502237. [arXiv:math.GR/0502237]. 1.2
[24] * M ARTIN K ASSABOV AND N IKOLAY N IKOLOV: Universal lattices and property τ.
arxiv:math.GR/0502112. [arXiv:math.GR/0502112]. 1.2
[25] * DAVID K AZHDAN: On the connection of the dual space of a group with the structure of its closed
subgroups (Russian). Funkcional. Anal. i Prilozh., 1:71–74, 1967. 1.2
[26] * M ARIA K LAWE: Limitations on explicit constructions of expanding graphs. SIAM J. Comput.,
13(1):156–166, 1984. [SICOMP:13/0213011]. 1.2
[27] * L ÁSZL Ó L OV ÁSZ AND P ETER W INKLER: Mixing times. In Microsurveys in discrete probability
(Princeton, NJ, 1997), volume 41 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 85–
133. Amer. Math. Soc., Providence, RI, 1998. 1.2
[28] * A. L UBOTZKY AND B. W EISS: Groups and expanders. In Expanding graphs (Princeton, NJ,
1992), volume 10 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 95–109. Amer. Math.
Soc., Providence, RI, 1993. 1.2
[29] * A LEX L UBOTZKY, R ALPH P HILLIPS , AND P ETER S ARNAK: Ramanujan graphs. Combinator-
ica, 8(3):261–277, 1988. [Combinatorica:k285687344657q53]. 1.1
[30] * A LEXANDER L UBOTZKY: Discrete groups, expanding graphs and invariant measures.
Birkhäuser Verlag, Basel, 1994. 1.1, 8
[31] * A LEXANDER L UBOTZKY AND I GOR PAK: The product replacement algorithm and Kazhdan’s
property (T). Journal of the American Mathematical Society, 14(2):347–363 (electronic), 2001.
[JAMS:2001-14-02/S0894-0347-00-00356-8]. 1.1
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 117
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
[32] * G REGORY A. M ARGULIS: Explicit constructions of expanders. Problemy Peredači Informacii,
9(4):71–80, 1973. 1.1
[33] * G REGORY A. M ARGULIS: Explicit group-theoretic constructions of combinatorial schemes and
their applications in the construction of expanders and concentrators. Problemy Peredachi Infor-
matsii, 24(1):51–60, 1988. 1.1
[34] * ROY M ESHULAM AND AVI W IGDERSON: Expanders from symmetric codes. In Proc. of
the 34th Annual ACM Symposium on Theory of Computing, pp. 669–677. ACM Press, 2002.
[STOC:509907.510004]. 1.2
[35] * M OSHE M ORGENSTERN: Existence and explicit constructions of q + 1 regular Ramanujan
graphs for every prime power q. Journal of Combinatorial Theory. Series B, 62(1):44–62, 1994.
[JCombThB:10.1006/jctb.1994.1054]. 1.1
[36] * J OSEPH NAOR AND M ONI NAOR: Small-bias probability spaces: Efficient constructions and
applications. SIAM Journal on Computing, 22(4):838–856, August 1993. [SICOMP:22/0222053].
1.1
[37] * N IKOLAY N IKOLOV: On the commutator width of perfect groups. Bull. London Math. Soc.,
36(1):30–36, 2004. [BLMS:10.1112/S0024609303002601]. 1.3, 2.2.3, 2.13, 6, 6.5, 6
[38] * OYSTEIN O RE: Some remarks on commutators. Proc. Amer. Math. Soc., 2:307–314, 1951. 3.1
[39] * M ARK S. P INSKER: On the complexity of a concentrator. In Proc. of the 7th Annual Teletraffic
Conference, pp. 318/1–318/4, Stockholm, 1973. 1.1
[40] * N ICHOLAS P IPPENGER: Sorting and selecting in rounds. SIAM Journal on Computing,
16(6):1032–1038, December 1987. [SICOMP:16/0216066]. 1.1
[41] * N ICHOLAS P IPPENGER AND A NDREW C. YAO: Rearrangeable networks with limited depth.
SIAM Journal on Algebraic and Discrete Methods, 3(4):411–417, 1982. [SIMAX:03/0603041].
1.1
[42] * O MER R EINGOLD , S ALIL VADHAN , AND AVI W IGDERSON: Entropy waves, the zig-zag
graph product, and new constant-degree expanders. Ann. of Math. (2), 155(1):157–187, 2002.
[arXiv:math.CO/0406038]. 1.1, 1.3, 2.2.2, 7, 7.9
[43] * ATLE S ELBERG: On the estimation of Fourier coefficients of modular forms. In Proc. of the
Sympos. Pure Math., volume VIII, pp. 1–15. Amer. Math. Soc., Providence, R.I., 1965. 1.2
[44] * M ICHAEL S IPSER: Expanders, randomness, or time versus space. Journal of Computer and
System Sciences, 36(3):379–383, June 1988. [JCSS:10.1016/0022-0000(88)90035-9]. 1.1
[45] * M ICHAEL S IPSER AND DANIEL A. S PIELMAN: Expander codes. IEEE Transactions on Infor-
mation Theory, 42(6, part 1):1710–1722, 1996. [TIT:10.1109/18.556667]. 1.1
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 118
I TERATIVE C ONSTRUCTION OF C AYLEY E XPANDER G RAPHS
[46] * DANIEL A. S PIELMAN: Linear-time encodable and decodable error-correcting codes. IEEE
Transactions on Information Theory, 42(6, part 1):1723–1731, 1996. [TIT:10.1109/18.556668].
1.1
[47] * M ICHAEL R. TANNER: Explicit concentrators from generalized n-gons. SIAM Journal on Alge-
braic Discrete Methods, 5(3):287–293, 1984. [SIMAX:05/0605030]. 1.1
[48] * A LASDAIR U RQUHART: Hard examples for resolution. Journal of the Association for Comput-
ing Machinery, 34(1):209–219, 1987. [JACM:7531.8928]. 1.1
[49] * L ESLIE G. VALIANT: Graph-theoretic arguments in low-level complexity. In Proc. of the 6th
Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in
Comput. Sci., pp. 162–176. Springer, Berlin, 1977. 1.1
[50] * AVI W IGDERSON AND DAVID Z UCKERMAN: Expanders that beat the eigenvalue bound:
explicit construction and applications. Combinatorica, 19(1):125–138, 1999. [Combinator-
ica:wcjlnyjmdxf30b9x]. 1.1
AUTHORS
Eyal Rozenman
Postdoc
School of Mathematics
Institute for Advanced Study, Princeton
eyal ias edu
http://www.math.ias.edu/~eyal
Aner Shalev
Professor
Einstein Institute of Mathematics
The Hebrew University of Jerusalem
shalev math huji ac il
http://www.ma.huji.ac.il
Avi Wigderson
Professor
School of Mathematics
Institute for Advanced Study, Princeton
avi ias edu
http://www.math.ias.edu/~avi
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 119
E. ROZENMAN , A. S HALEV, AND A. W IGDERSON
ABOUT THE AUTHORS
E YAL ROZENMAN is currently a member in the Institute for Advanced Study, Princeton.
He grew up near Tel Aviv, Israel, went to Tel Aviv University for his B. Sc. degree, and
received his Ph. D. from the Hebrew University under the guidance of Nathan Linial.
Eyal’s research interests include groups, expanders and their interaction, and pseudo-
randomness in general. He loves to read and write papers which are elementary, but
he likes them better if they contain fancy mathematical notions. Eyal’s non-research
interests include hiking, reading, and avoiding driving.
A NER S HALEV was born in the previous century in a kibbutz on the Sea of Galilee. His
first love (at 10) was experimental chemistry, which proved too dangerous when a test
tube full of hydrogen exploded in his hands. He wisely moved to pure mathematics and
writing fiction.
In 1988 he finished his Ph. D. in mathematics at the Hebrew University of Jerusalem,
supervised by Shimshon Amitsur and Avinoam Mann, and published his first book,
Opus 1 - a collection of stories with a musical structure. Other literary works followed:
Overtures (1996) - seventy openings of stories without ends, and the recent novel Dark
Matter (2004), a complex love story with astrophysical parallels, alternating between
prose and email, which will also appear in some European languages.
The mathematical work of Aner Shalev is in algebra. He enjoys studying groups using
other disciplines, such as Lie methods and probabilistic methods. He was an invited
ICM speaker (1998), and chaired the Institute of Mathematics at the Hebrew University
(1999-2001). He used to enjoy playing chess with his daughter Ariella until he started
losing.
AVI W IGDERSON was born in Haifa, Israel in 1956, and received his Ph. D. in 1983 at
Princeton University under Dick Lipton. He enjoys and is fascinated with studying the
power and limits of efficient computation, and the remarkable impacts of this field on
understanding our world. Avi’s other major source of fascination and joy are his three
kids, Eyal, Einat, and Yuval.
T HEORY OF C OMPUTING, Volume 2 (2006), pp. 91–120 120