Electronic Research Announcements

Author(s): 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
Posted: June 9, 2005
Retrieve article in: PDF DVI PostScript

Abstract: We construct explicit generating sets

and $\tilde F_n$ of the alternating and the symmetric groups, which turn the Cayley graphs $\mathcal{C}({Alt}(n), F_n)$ and $\mathcal{C}({Sym}(n), \tilde F_n)$ into a family of bounded degree expanders for all sufficiently large

. These expanders have many applications in the theory of random walks on groups and in other areas of mathematics.

1.: M. Abért, Symmetric groups as products of abelian subgroups, Bull. London Math. Soc. 34 (2002), no. 4, 451-456. MR 1897424 (2002m:20006)
2.: 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. MR 1948752
3.: N. Alon and Y. Roichman, Random Cayley graphs and expanders, Random Structures Algorithms 5 (1994), no. 2, 271-284. MR 1262979 (94k:05132)
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. MR 1150735
5.: 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. MR 1022771 (91a:20038)
6.: M. Burger, Kazhdan constants for ${\rm SL}(3,{\mathbb{Z} })$ , J. Reine Angew. Math. 413 (1991), 36-67. MR 1089795 (92c:22013)
7.: R. Gilman, Finite quotients of the automorphism group of a free group, Canad. J. Math. 29 (1977), no. 3, 541-551. MR 0435226 (55:8186)
8.: M. Kassabov, Kazhdan constants for ${\mathrm{SL}}_n(\mathbb{Z} )$ , arXiv:math.GR/0311487.
9.: M. Kassabov, Symmetric groups and expanders, in preparation.
10.: M. Kassabov, Universal lattices and unbounded rank expanders, arXiv:math.GR/0502237.
11.: M. Kassabov and N. Nikolov, Finite simple groups and expanders, in preparation.
12.: M. Kassabov and T. R. Riley, Diameters of Cayley graphs of ${\mathrm{SL}}_n(\mathbb{Z} /k\mathbb{Z} )$ , arXiv:math.GR/0502221.
13.: 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. MR 0209390 (35:288)
14.: 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). MR 2097328
15.: P. Loh and L. Schulman, Improved expansion of random cayley graphs, Disc. Math. and Theor. Comp. Sci. 6 (2004), 523-528. MR 2097328
16.: A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261-277. MR 963118 (89m:05099)
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. MR 1235570 (95b:05097)
18.: A. Lubotzky, private communication.
19.: A. Lubotzky, Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, vol. 125, Birkhäuser Verlag, Basel, 1994. MR 1308046 (96g:22018)
20.: 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. MR 1358635 (96k:05081)
21.: 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). MR 1815215 (2003d:60012)
22.: A. Lubotzky and A. Zuk, On property $\tau$ , preprint. http://www.ma.huji.ac.il/ alexlub/BOOKS/On%20property/On%20property.pdf
23.: G. A. Margulis, Explicit constructions of expanders, Problemy Peredachi Informatsii 9 (1973), no. 4, 71-80. MR 0484767 (58:4643)
24.: N. Nikolov, private communication.
25.: 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. MR 1931799
26.: Y. Roichman, Upper bound on the characters of the symmetric groups, Invent. Math. 125 (1996), no. 3, 451-485. MR 1400314 (97e:20014)
27.: Y. Roichman, Expansion properties of Cayley graphs of the alternating groups, J. Combin. Theory Ser. A 79 (1997), no. 2, 281-297. MR 1462559 (98g:05070)
28.: 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. MR 2121630
29.: Y. Shalom, Bounded generation and Kazhdan's property (T), Inst. Hautes Études Sci. Publ. Math. no. 90 (1999), 145-168 (2001). MR 1813225 (2001m:22030)

Martin Kassabov
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853-4201
Email: kassabov@math.cornell.edu

DOI: 10.1090/S1079-6762-05-00146-0
PII: S 1079-6762(05)00146-0
Keywords: Expanders, symmetric groups, alternating groups, random permutations, property T, Kazhdan constants.
Received by editor(s): March 16, 2005
Posted: June 9, 2005
Communicated by: Efim Zelmanov
Copyright of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1079-6762

Previous volume \| Table of contents \| Next volume Articles in press \| Most recent volume \| All volumes Previous Article \| Next Article

Currently published by the American Institute of Mathematical Sciences as Electronic Research Announcements in Mathematical Sciences


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS