Geodesic
Symmetric groups and expanders
Kassabov, Martin1
1 Department of Mathematics, Cornell University, Ithaca, New York 14853-4201
Electronic research announcements of the American Mathematical Society, Tome 11 (2005), pp. 47-56 Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

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.
DOI : 10.1090/S1079-6762-05-00146-0

Kassabov, Martin 1

1 Department of Mathematics, Cornell University, Ithaca, New York 14853-4201 
@article{10_1090_S1079_6762_05_00146_0,
     author = {Kassabov, Martin},
     title = {Symmetric groups and expanders},
     journal = {Electronic research announcements of the American Mathematical Society},
     pages = {47--56},
     year = {2005},
     volume = {11},
     doi = {10.1090/S1079-6762-05-00146-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-05-00146-0/}
}
TY  - JOUR
AU  - Kassabov, Martin
TI  - Symmetric groups and expanders
JO  - Electronic research announcements of the American Mathematical Society
PY  - 2005
SP  - 47
EP  - 56
VL  - 11
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-05-00146-0/
DO  - 10.1090/S1079-6762-05-00146-0
ID  - 10_1090_S1079_6762_05_00146_0
ER  - 
%0 Journal Article
%A Kassabov, Martin
%T Symmetric groups and expanders
%J Electronic research announcements of the American Mathematical Society
%D 2005
%P 47-56
%V 11
%U http://geodesic.mathdoc.fr/articles/10.1090/S1079-6762-05-00146-0/
%R 10.1090/S1079-6762-05-00146-0
%F 10_1090_S1079_6762_05_00146_0
Kassabov, Martin. Symmetric groups and expanders. Electronic research announcements of the American Mathematical Society, Tome 11 (2005), pp. 47-56. doi: 10.1090/S1079-6762-05-00146-0

[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

Cité par Sources :