Symmetric groups and expanders

Kassabov, Martin¹

¹ Department of Mathematics, Cornell University, Ithaca, New York 14853-4201

Electronic research announcements of the American Mathematical Society, Tome 11 (2005), pp. 47-56.

Résumé

We construct explicit generating sets $F_n$ and $\tilde F_n$ of the alternating and the symmetric groups, which turn the Cayley graphs $\mathcal {C}(\mathrm {Alt}(n), F_n)$ and $\mathcal {C}(\mathrm {Sym}(n), \tilde F_n)$ into a family of bounded degree expanders for all sufficiently large $n$. These expanders have many applications in the theory of random walks on groups and in other areas of mathematics.

Détail

DOI : 10.1090/S1079-6762-05-00146-0

Bibliographie

[1] Abért, Miklós Symmetric groups as products of abelian subgroups Bull. London Math. Soc. 2002 451 456

[2] Alon, Noga, Lubotzky, Alexander, Wigderson, Avi Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract) 2001 630 637

[3] Alon, Noga, Roichman, Yuval Random Cayley graphs and expanders Random Structures Algorithms 1994 271 284

[4] Babai, L., Hetyei, G., Kantor, W. M., Lubotzky, A., Seress, Á. On the diameter of finite groups 1990 857 865

[5] Babai, L., Kantor, W. M., Lubotsky, A. Small-diameter Cayley graphs for finite simple groups European J. Combin. 1989 507 522

[6] Burger, M. Kazhdan constants for 𝑆𝐿(3,𝑍) J. Reine Angew. Math. 1991 36 67

[7] Gilman, Robert Finite quotients of the automorphism group of a free group Canadian J. Math. 1977 541 551

[8] Každan, D. A. On the connection of the dual space of a group with the structure of its closed subgroups Funkcional. Anal. i Priložen. 1967 71 74

[9] Landau, Zeph, Russell, Alexander Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem Electron. J. Combin. 2004

[10] Landau, Zeph, Russell, Alexander Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem Electron. J. Combin. 2004

[11] Lubotzky, A., Phillips, R., Sarnak, P. Ramanujan graphs Combinatorica 1988 261 277

[12] Lubotzky, A., Weiss, B. Groups and expanders 1993 95 109

[13] Lubotzky, Alexander Discrete groups, expanding graphs and invariant measures 1994

[14] Lubotzky, Alexander Cayley graphs: eigenvalues, expanders and random walks 1995 155 189

[15] Lubotzky, Alexander, Pak, Igor The product replacement algorithm and Kazhdan’s property (T) J. Amer. Math. Soc. 2001 347 363

[16] Margulis, G. A. Explicit constructions of expanders Problemy Peredači Informacii 1973 71 80

[17] Reingold, Omer, Vadhan, Salil, Wigderson, Avi Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors (extended abstract) 2000 3 13

[18] Roichman, Yuval Upper bound on the characters of the symmetric groups Invent. Math. 1996 451 485

[19] Roichman, Yuval Expansion properties of Cayley graphs of the alternating groups J. Combin. Theory Ser. A 1997 281 297

[20] Rozenman, Eyal, Shalev, Aner, Wigderson, Avi A new family of Cayley expanders (?) 2004 445 454

[21] Shalom, Yehuda Bounded generation and Kazhdan’s property (T) Inst. Hautes Études Sci. Publ. Math. 1999