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
A M. Abért, Symmetric groups as products of abelian subgroups, Bull. London Math. Soc. 34 (2002), no. 4, 451–456.
ALW N. Alon, A. Lubotzky, and A. 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.
AR N. Alon and Y. Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271–284.
BHKLS 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.
BLK L. Babai, W. M. Kantor, and A. Lubotzky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507–522.
Bur M. Burger, Kazhdan constants for $\textrm {SL}(3,{\mathbb {Z}})$, J. Reine Angew. Math. 413 (1991), 36–67.
Gilman R. Gilman, Finite quotients of the automorphism group of a free group, Canad. J. Math. 29 (1977), no. 3, 541–551.
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.
kazhdan D. A. Kazhdan, On the connection of the dual space of a group with the structure of its closed subgroups, Funktsional. Anal. i Prilozhen. 1 (1967), 71–74.
LR Z. Landau and A. 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 pp. (electronic).
LS P. Loh and L. Schulman, Improved expansion of random cayley graphs, Disc. Math. and Theor. Comp. Sci. 6 (2004), 523–528.
LPS A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277.
lubwiess 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.
Lpr A. Lubotzky, private communication.
expanderbook A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel, 1994.
lu A. 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.
LP A. Lubotzky and I. Pak, The product replacement algorithm and Kazhdan’s property (T), J. Amer. Math. Soc. 14 (2001), no. 2, 347–363 (electronic).
LubZuk A. Lubotzky and A. Żuk, On property $\tau$, preprint. http://www.ma.huji.ac.il/ alexlub/BOOKS/On%20property/On%20property.pdf
Mar G. A. Margulis, Explicit constructions of expanders, Problemy Peredachi Informatsii 9 (1973), no. 4, 71–80.
Npr N. Nikolov, private communication.
RVW O. Reingold, S. Vadhan, and A. 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.
Ro Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451–485.
Ro1 Y. Roichman, Expansion properties of Cayley graphs of the alternating groups, J. Combin. Theory Ser. A 79 (1997), no. 2, 281–297.
RSW E. Rozenman, Aner Shalev, and Avi Wigderson, A new family of Cayley expanders, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 445–454 (electronic), ACM, New York, 2004.
YSh Y. Shalom, Bounded generation and Kazhdan’s property (T), Inst. Hautes Études Sci. Publ. Math. no. 90 (1999), 145–168 (2001).
Similar Articles
Retrieve articles in Electronic Research Announcements of the American Mathematical Society
with MSC (2000):
20B30,
05C25,
05E15,
20C30,
20F69,
60C05,
68R05,
68R10
Retrieve articles in all journals
with MSC (2000):
20B30,
05C25,
05E15,
20C30,
20F69,
60C05,
68R05,
68R10
Additional Information
Martin Kassabov
Affiliation:
Department of Mathematics, Cornell University, Ithaca, New York 14853-4201
Email:
kassabov@math.cornell.edu
Keywords:
Expanders,
symmetric groups,
alternating groups,
random permutations,
property T,
Kazhdan constants.
Received by editor(s):
March 16, 2005
Published electronically:
June 9, 2005
Communicated by:
Efim Zelmanov
Article copyright:
© Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.