Theory of Computing
-------------------
Title     : Iterative Construction of Cayley Expander Graphs
Authors   : Eyal Rozenman, Aner Shalev, and Avi Wigderson
Volume    : 2
Number    : 5
Pages     : 91-120
URL       : https://theoryofcomputing.org/articles/v002a005

Abstract
--------

We construct a sequence of groups G_n, and explicit sets of
generators Y_n \subset G_n, such that all generating sets have
bounded size, and the associated Cayley graphs are all expanders. The
group G_1 is the alternating group A_d, the set of even
permutations on the elements {1,2,...,d}. The group G_n 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_infty
with generating set Y_infty, given with a mapping f_n from
G_infty to G_n for every n, which sends Y_infty to
Y_n. In particular, under the assumption described above,
G_infty has property (tau) with respect to the family of
subgroups ker(f_n).

The proof is elementary, using only simple combinatorics and linear
algebra. The recursive structure of the groups G_n (iterated wreath
products of the alternating group A_d) allows for an inductive proof
of expansion, using the group theoretic analogue (of Alon et 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 A_d.

Essential use is made of the fact that our groups have the 
commutator property: every 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 generating sets Y_n 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.