×

Symmetric groups and expanders. (English) Zbl 1077.20001

Summary: We construct explicit generating sets \(F_n\) and \(\widetilde F_n\) of the alternating and the symmetric groups, which turn the Cayley graphs \({\mathcal C}(\text{Alt}(n),F_n)\) and \({\mathcal C}(\text{Sym}(n),\widetilde 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.

MSC:

20B30 Symmetric groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20F05 Generators, relations, and presentations of groups
60G50 Sums of independent random variables; random walks
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML EMIS

References:

[1] Miklós Abért, Symmetric groups as products of abelian subgroups, Bull. London Math. Soc. 34 (2002), no. 4, 451 – 456. · Zbl 1035.20001 · doi:10.1112/S0024609302001042
[2] 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.
[3] Noga Alon and Yuval Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271 – 284. · Zbl 0798.05048 · doi:10.1002/rsa.3240050203
[4] 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. · doi:10.1109/FSCS.1990.89608
[5] 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. · Zbl 0702.05042 · doi:10.1016/S0195-6698(89)80067-8
[6] M. Burger, Kazhdan constants for \?\?(3,\?), J. Reine Angew. Math. 413 (1991), 36 – 67. · Zbl 0704.22009 · doi:10.1515/crll.1991.413.36
[7] Robert Gilman, Finite quotients of the automorphism group of a free group, Canad. J. Math. 29 (1977), no. 3, 541 – 551. · Zbl 0332.20010 · doi:10.4153/CJM-1977-056-3
[8] M. Kassabov, Kazhdan constants for \({\mathrm{SL}}_n(\mathbb{Z} )\), arXiv:math.GR/0311487. · Zbl 1097.22007
[9] M. Kassabov, Symmetric groups and expanders, in preparation. · Zbl 1140.20039
[10] M. Kassabov, Universal lattices and unbounded rank expanders, arXiv:math.GR/0502237. · Zbl 1140.20039
[11] M. Kassabov and N. Nikolov, Finite simple groups and expanders, in preparation. · Zbl 1161.20010
[12] M. Kassabov and T. R. Riley, Diameters of Cayley graphs of \({\mathrm{SL}}_n(\mathbb{Z} /k\mathbb{Z} )\), arXiv:math.GR/0502221. · Zbl 1116.05035
[13] 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).
[14] 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. · Zbl 1053.05060
[15] 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. · Zbl 1053.05060
[16] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261 – 277. · Zbl 0661.05035 · doi:10.1007/BF02126799
[17] 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. · Zbl 0787.05049
[18] A. Lubotzky, private communication.
[19] 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. · Zbl 0826.22012
[20] 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. · Zbl 0835.05033 · doi:10.1017/CBO9780511662096.008
[21] Alexander Lubotzky and Igor Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347 – 363. · Zbl 0980.20078
[22] A. Lubotzky and A. Zuk, On property \(\tau\), preprint. http://www.ma.huji.ac.il/ alexlub/BOOKS/On
[23] G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71 – 80 (Russian). · Zbl 0312.22011
[24] N. Nikolov, private communication.
[25] 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. · Zbl 1008.05101 · doi:10.1109/SFCS.2000.892006
[26] Yuval Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451 – 485. · Zbl 0854.20015 · doi:10.1007/s002220050083
[27] Yuval Roichman, Expansion properties of Cayley graphs of the alternating groups, J. Combin. Theory Ser. A 79 (1997), no. 2, 281 – 297. · Zbl 0881.05058 · doi:10.1006/jcta.1997.2786
[28] 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. · Zbl 1192.68862 · doi:10.1145/1007352.1007423
[29] Yehuda Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. 90 (1999), 145 – 168 (2001). · Zbl 0980.22017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.