We explicitly construct a new family of constant-degree Cayley expander graphs, under the (yet unproved) assumption that the symmetric group S_d has d^{1/30} generators such that the resulting Cayley graph is an expander.
The underlying groups are the iterated wreath products of the alternating group A_d for some fixed d. The key property of these groups is that every element in them is a commutator, and the representation as a commutator can be computed efficiently (implicit in Nikolov '02).
The expanding generating sets are constructed inductively, using the "zig-zag" lemma of Reingold et al. (Annals '01), in its algebraic version given by Alon et al. (FOCS '01). The base of the induction is a small expanding generating set in A_d, which is the unproved assumption of the construction.
An essential part is the analysis of the expansion of a Cayley graph on two copies of a group GxG with (perfectly correlated) set of generators of the form (g, g^{-1}), when all elements of G are commutators.
The main open problem is to prove the conjecture on which the construction is based: For some finite (sufficiently large) k, there exists a set of k^{1/30} permutations in S_k, such that the resulting Cayley graph is an expander.
Joint work with Avi Wigderson (IAS).
Copyright. All Rights Reserved.