Volume 2 (2006)
Article 5 pp. 91-120
Iterative Construction of Cayley Expander Graphs
by Eyal Rozenman, Aner Shalev, and Avi Wigderson
Received: July 24, 2005
Published: April 25, 2006
Keywords: Cayley graph, expanders, expander graphs, wreath products
ACM Classification: G.2.2, G.3
AMS Classification: 05C25, 37A30
Abstract:
[Plain Text Version]
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 recursive 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 (by 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 Ad.
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
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.