Iterative construction of Cayley Expander graphsEyal Rozenman∗Aner Shalev†Avi Wigderson‡.AbstractWe construct a sequence of groups Gn, and explicit sets of generators Yn⊂ Gn, such thatall generating sets have bounded size, and the associated Cayley graphs are all expanders.The group G1is the alternating group Ad, the set of even permutations on the elements{1, 2, . . . , d}. The group Gnis the group of all even symmetries of the rooted d-regular tree ofdepth n. Our results hold for any large enough d.We also describe a finitely-generated infinite group G∞with generating set Y∞, givenwith a mapping fnfrom G∞to Gnfor every n, which sends Y∞to Yn. In particular, underthe assumption described above, G∞has property (τ) with respect to the family of subgroupsker(fn).The proof is elementary, using only simple combinatorics and linear algebra. The recursivestructure of the groups Gn(iterated wreath products of the alternating group Ad) allows for aninductive proof of expansion, using the group theoretic analogue [4] of the zig-zag graph prod-uct of [42]. The basis of the inductive proof is a recent result by Kassabov [22] on expandinggenerating sets for the group Ad.Essential use is made of the fact that our groups have the commutator property: everyelement is a commutator. We prove that direct products of such groups are expanding evenwith highly correlated tuples of generators. Equivalently, highly dependent random walks onseveral copies of these groups converge to stationarity on all of them essentially as quicklyas independent random walks. Moreover, our explicit construction of the generating sets Ynabove uses an efficient algorithm for solving certain equations over these groups, which relieson the work of [37] on the commutator width of perfect groups.∗The Hebrew university, Jerusalem. E-mail: [email protected]. Part of this research was performedwhile visiting the Institute for Advanced Study, Princeton, NJ.†The Hebrew university, Jerusalem. E-mail: [email protected]. Partially supported by BSF grant2000-53 and a grant from the Israel Science Foundation‡Institute for Advanced Study, Princeton. E-mail: [email protected] Partially supported by NSF grant CCR-032490611 Introduction1.1 Expander GraphsExpanders are graphs which are sparse but nevertheless highly connected. Expanders graphshave been used to solve many fundamental problems in computer science, in topics includingnetwork 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 foundsome 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 wetake the most stringent definition of explicitness of an infinite family of graphs, requiring thata 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 explicitconstruction led to an exciting and extensive body of research.Most of this work was guided by the algebraic characterization of expanders, developedin [47, 5, 2]. They showed the intimate relation of (appropriate quantitative versions of) thecombinatorial (isoperimetric) notion of expansion above, to the spectral gap in the adjacencymatrix (or, almost equivalently, the Laplacian) of the graph. This relationship is tight enoughfor 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 expanderfamily if for all of them the second largest eigenvalue of the normalized adjacency (i.e. randomwalk) matrix is bounded above by the same constant that is smaller than 1.This algebraic definition of expanders by eigenvalues naturally led researchers to consideralgebraic constructions, where this eigenvalue can be estimated. The celebrated sequence ofpapers [32, 14, 5, 3, 20, 29, 33, 35] provided such highly explicit families of constant-degreeexpanders. All of these constructions are based on groups, and their analysis often appeals todeep results in mathematics.The algebraic mould was broken recently by [42], where a simple, combinatorial construc-tion of constant-degree expander graphs was presented. The construction is iterative, generat-ing the next graph in the family from two previous ones via a novel graph product, the zig-zagproduct. This product was proved (using simple linear algebra) to simultaneously keep thedegree small, and retain expansion. Thus the iteration process need only be provided with aninitial, fixed size expander “seed” graph , from which all others are generated. The requiredparameters of the seed graph are easily shown to hold for a random graph (which suffices forexplicitness - 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 Cay-ley graph is based on the group Ad, the group of even permutations on the set {1, 2, . . . , d}. Ina recent breakthrough, Kassabov [22] explicitly constructed a bounded-size, expanding gener-ating 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 ex-pansion, and its relations to yet unexplored mathematical structures. It also further explores thepower 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 Cayley2expanders.1.2 Expanding Cayley graphsFor a finite group H and a (symmetric) set of elements T in it, the Cayley graph C(H; T ) hasthe elements of H as vertices, and edges connect a pair of vertices g, h if their “ratio” gh−1isin T . We remark that while most applications do not require the expanders to be “Cayley”, therecent paper [7] seems to essentially require Cayley expanders to achieve nearly linear-sizedlocally testable codes (LTCs) and probabilistically checkable proof (PCPs).Many of the algebraic expander constructions mentioned above