Symmetric groups and expanders

Kassabov, Martin

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

Symmetric groups and expanders

Author: Martin Kassabov
Journal: Electron. Res. Announc. Amer. Math. Soc. 11 (2005), 47-56
MSC (2000): Primary 20B30; Secondary 05C25, 05E15, 20C30, 20F69, 60C05, 68R05, 68R10
DOI: https://doi.org/10.1090/S1079-6762-05-00146-0
Published electronically: June 9, 2005
MathSciNet review: 2150944
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

Miklós Abért, Symmetric groups as products of abelian subgroups, Bull. London Math. Soc. 34 (2002), no. 4, 451–456. MR 1897424, DOI https://doi.org/10.1112/S0024609302001042
Noga Alon, Alexander Lubotzky, and Avi Wigderson, Semi-direct product in groups and zig-zag product in graphs: connections and applications (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) IEEE Computer Soc., Los Alamitos, CA, 2001, pp. 630–637. MR 1948752
Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284. MR 1262979, DOI https://doi.org/10.1002/rsa.3240050203
L. Babai, G. Hetyei, W. M. Kantor, A. Lubotzky, and Á. Seress, On the diameter of finite groups, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990) IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 857–865. MR 1150735, DOI https://doi.org/10.1109/FSCS.1990.89608
L. Babai, W. M. Kantor, and A. Lubotsky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507–522. MR 1022771, DOI https://doi.org/10.1016/S0195-6698%2889%2980067-8
M. Burger, Kazhdan constants for ${\rm SL}(3,{\bf Z})$, J. Reine Angew. Math. 413 (1991), 36–67. MR 1089795, DOI https://doi.org/10.1515/crll.1991.413.36
Robert Gilman, Finite quotients of the automorphism group of a free group, Canadian J. Math. 29 (1977), no. 3, 541–551. MR 435226, DOI https://doi.org/10.4153/CJM-1977-056-3

K M. Kassabov, Kazhdan constants for ${\mathrm {SL}}_n(\mathbb {Z})$, arXiv:math.GR/0311487.

Ksymfull M. Kassabov, Symmetric groups and expanders, in preparation.

KSL3k M. Kassabov, Universal lattices and unbounded rank expanders, arXiv:math.GR/0502237.

KNFS M. Kassabov and N. Nikolov, Finite simple groups and expanders, in preparation.

KR M. Kassabov and T. R. Riley, Diameters of Cayley graphs of ${\mathrm {SL}}_n(\mathbb {Z}/k\mathbb {Z})$, arXiv:math.GR/0502221.

D. A. Každan, On the connection of the dual space of a group with the structure of its closed subgroups, Funkcional. Anal. i Priložen. 1 (1967), 71–74 (Russian). MR 0209390
Zeph Landau and Alexander Russell, Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem, Electron. J. Combin. 11 (2004), no. 1, Research Paper 62, 6. MR 2097328
Zeph Landau and Alexander Russell, Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem, Electron. J. Combin. 11 (2004), no. 1, Research Paper 62, 6. MR 2097328
A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI https://doi.org/10.1007/BF02126799
A. Lubotzky and B. Weiss, Groups and expanders, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 95–109. MR 1235570, DOI https://doi.org/10.1090/dimacs/010/08

Lpr A. Lubotzky, private communication.

Alexander Lubotzky, Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel, 1994. With an appendix by Jonathan D. Rogawski. MR 1308046
Alexander Lubotzky, Cayley graphs: eigenvalues, expanders and random walks, Surveys in combinatorics, 1995 (Stirling), London Math. Soc. Lecture Note Ser., vol. 218, Cambridge Univ. Press, Cambridge, 1995, pp. 155–189. MR 1358635, DOI https://doi.org/10.1017/CBO9780511662096.008
Alexander Lubotzky and Igor Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363. MR 1815215, DOI https://doi.org/10.1090/S0894-0347-00-00356-8

LubZuk A. Lubotzky and A. Żuk, On property $\tau$, preprint. http://www.ma.huji.ac.il/ alexlub/BOOKS/On%20property/On%20property.pdf

G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71–80 (Russian). MR 0484767

Npr N. Nikolov, private communication.

Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors (extended abstract), 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000) IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, pp. 3–13. MR 1931799, DOI https://doi.org/10.1109/SFCS.2000.892006
Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451–485. MR 1400314, DOI https://doi.org/10.1007/s002220050083
Yuval Roichman, Expansion properties of Cayley graphs of the alternating groups, J. Combin. Theory Ser. A 79 (1997), no. 2, 281–297. MR 1462559, DOI https://doi.org/10.1006/jcta.1997.2786
Eyal Rozenman, Aner Shalev, and Avi Wigderson, A new family of Cayley expanders (?), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, ACM, New York, 2004, pp. 445–454. MR 2121630, DOI https://doi.org/10.1145/1007352.1007423
Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145–168 (2001). MR 1813225