×

Iterative construction of Cayley expander graphs. (English) Zbl 1213.05127

Summary: 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,\ldots ,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 \(\text{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 by N Alon, A. Lubotzky and A. Widgerson [in: Proceedings of the 42nd annual symposium on foundations of computer science, 630–637 (2001)] of the zig-zag graph product [O. Reingold, S. Vadhan and A. Wigderson, Ann. Math. (2) 155, No. 1, 157–187 (2002; Zbl 1008.05101)].
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.

MSC:

05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1008.05101
PDFBibTeX XMLCite
Full Text: DOI