On the diameter of permutation groups

Abstract

Given a finite group $G$ and a set $A$ of generators, the diameter
$\mathrm{diam}(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\mathrm{diam}(G):= \mathrm{max}_A\mathrm{diam}(\Gamma(G,A))$.
It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$, but the best previously known upper bound was exponential in $\sqrt{n \log n}$. We give a quasipolynomial upper bound, namely, \[\mathrm{diam}(G) = \mathrm{exp}\left(O((\log n)^4 \log\log n)\right) = \mathrm{exp}\left((\log \log |G|)^{O(1)}\right)\] for $G = \mathrm{Sym}(n)$ or $G = \mathrm{Alt}(n)$, where the implied constants are absolute. This addresses a key open case of Babai’s conjecture on diameters of simple groups. By a result of Babai and Seress (1992), our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree $n$.

  • [Aldous] Go to document D. Aldous, "On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing," Prob. Engng. Info. Sci., vol. 1, pp. 33-46, 1987.
    @article{Aldous,
      author={Aldous, D.},
      TITLE={On the {M}arkov chain simulation method for uniform combinatorial distributions and simulated annealing},
      JOURNAL={Prob. Engng. Info. Sci.},
      VOLUME={1},
      YEAR={1987},
      PAGES={33--46},
      DOI = {10.1017/S0269964800000267},
     }
  • [Bab82] Go to document L. Babai, "On the order of doubly transitive permutation groups," Invent. Math., vol. 65, iss. 3, pp. 473-484, 1981/82.
    @article {Bab82, MRKEY = {0643565},
      AUTHOR = {Babai, L{á}szl{ó}},
      TITLE = {On the order of doubly transitive permutation groups},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {65},
      YEAR = {1981/82},
      NUMBER = {3},
      PAGES = {473--484},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {20B20 (20B35)},
      MRNUMBER = {0643565},
      MRREVIEWER = {W. Narkiewicz},
      DOI = {10.1007/BF01396631},
      ZBLNUMBER = {0478.20002},
     }
  • [Babtech] L. Babai, "Local expansion of vertex transitive graphs and random generation in finite groups," in 23rd ACM Symposium on Theory of Computing, New York: ACM Press, 1991, pp. 164-174.
    @incollection{Babtech,
      author={Babai, L{á}szl{ó}},
      TITLE = {Local expansion of vertex transitive graphs and random generation in finite groups},
      BOOKTITLE={23rd {A}{C}{M} {S}ymposium on {T}heory of {C}omputing},
      PUBLISHER={{A}{C}{M} {P}ress},
      ADDRESS={New York},
      YEAR={1991},
      PAGES={164--174},
      ZBLNUMBER = {10.1145/103418.103440},
     }
  • [MR2368881] Go to document L. Babai, "On the diameter of Eulerian orientations of graphs," in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2006, pp. 822-831.
    @inproceedings {MR2368881, MRKEY = {2368881},
      AUTHOR = {Babai, L{á}szl{ó}},
      TITLE = {On the diameter of {E}ulerian orientations of graphs},
      BOOKTITLE = {Proceedings of the {S}eventeenth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      PAGES = {822--831},
      PUBLISHER = {ACM Press},
      ADDRESS = {New York},
      YEAR = {2006},
      MRCLASS = {05C45 (05C12)},
      MRNUMBER = {2368881},
      DOI = {10.1145/1109557.1109648},
      ZBLNUMBER = {1192.05084},
     }
  • [BCFLS] L. Babai, G. Cooperman, L. Finkelstein, L. E. M., and Á. Seress, "Fast Monte-Carlo algorithms for permutation groups," in 23rd ACM Symposium on Theory of Computing, New York, NY: ACM Press, 1991, pp. 90-100.
    @incollection{BCFLS,
      author = {Babai, L{á}szl{ó} and Cooperman, G. and Finkelstein, L. and Luks. E. M. and Seress, Á. },
      TITLE ={Fast {M}onte-{C}arlo algorithms for permutation groups},
      BOOKTITLE = {23rd {A}{C}{M} {S}ymposium on {T}heory of {C}omputing},
      YEAR = {1991},
      PAGES = {90--100},
      PUBLISHER = {{A}{C}{M} {P}ress},
      ADDRESS = {New York, NY},
      }
  • [BBS04] L. Babai, R. Beals, and &. Seress, "On the diameter of the symmetric group: polynomial bounds," in Proceedings of the Fifteenth Annual ACM–SIAM Symposium on Discrete Algorithms, New York, 2004, pp. 1108-1112.
    @inproceedings {BBS04, MRKEY = {2291003},
      AUTHOR = {Babai, L{á}szl{ó} and Beals, Robert and Seress, {Á}kos},
      TITLE = {On the diameter of the symmetric group: polynomial bounds},
      BOOKTITLE = {Proceedings of the {F}ifteenth {A}nnual {ACM}--{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      PAGES = {1108--1112},
      PUBLISHER = {ACM Press},
      ADDRESS = {New York},
      YEAR = {2004},
      MRCLASS = {20B30},
      MRNUMBER = {2291003},
      }
  • [BH] L. Babai and T. P. Hayes, "Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group," in Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, 2005, pp. 1057-1066.
    @inproceedings {BH, MRKEY = {2298365},
      AUTHOR = {Babai, L{á}szl{ó} and Hayes, Thomas P.},
      TITLE = {Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group},
      BOOKTITLE = {Proceedings of the {S}ixteenth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms},
      PAGES = {1057--1066},
      PUBLISHER = {ACM Press},
      ADDRESS = {New York},
      YEAR = {2005},
      MRCLASS = {05A05},
      MRNUMBER = {2298365},
      }
  • [BHKLS] Go to document L. Babai, G. Hetyei, W. ~M. Kantor, A. Lubotzky, and Á. Seress, "On the diameter of finite groups," in 31st Annual Symposium on Foundations of Computer Science, Vol. I, II, Los Alamitos, CA: IEEE Comput. Soc. Press, 1990, pp. 857-865.
    @incollection{BHKLS, MRKEY={1150735},
      AUTHOR={Babai, L{á}szl{ó} and Hetyei, G. and Kantor, W.~M. and Lubotzky, A. and Seress, {Á}.},
      TITLE={On the diameter of finite groups},
      BOOKTITLE={31st {A}nnual {S}ymposium on {F}oundations of {C}omputer {S}cience, {V}ol. {I},
      {II}},
      VENUE={St. Louis, MO, 1990},
      PUBLISHER={IEEE Comput. Soc. Press},
      ADDRESS={Los Alamitos, CA},
      YEAR={1990},
      PAGES={857--865},
      MRNUMBER={1150735},
      DOI={10.1109/FSCS.1990.89608},
     }
  • [BLS87] Go to document L. Babai, E. M. Luks, and Á. Seress, "Permutation groups in NC," in Proceedings of the Nineteenth Annual ACM Symposium on the Theory of Computing, New York, 1987, pp. 409-420.
    @inproceedings{BLS87,
      author = {Babai, L{á}szl{ó} and E. M. Luks and {Á}. Seress},
      TITLE = {Permutation groups in {N}{C}},
      BOOKTITLE = {Proceedings of the {N}ineteenth {A}nnual {ACM} {S}ymposium on the {T}heory of {C}omputing},
      PAGES = {409--420},
      PUBLISHER = {ACM Press},
      ADDRESS = {New York},
      YEAR = {1987},
      DOI = {10.1145/28395.28439},
     }
  • [BLS88] Go to document L. Babai, E. M. Luks, and Á. Seress, "Fast management of permutation groups," in Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, Singer Island, FL, 1988, pp. 272-282.
    @inproceedings{BLS88,
      author = {Babai, L{á}szl{ó} and E. M. Luks and Á. Seress},
      TITLE = {Fast management of permutation groups},
      BOOKTITLE = {Proceedings of the 29th IEEE Symposium on Foundations of Computer Science},
      PAGES = {272--282},
      PUBLISHER = {IEEE Computer Society Press},
      ADDRESS = {Singer Island, FL},
      YEAR = {1988},
      DOI = {10.1109/SFCS.1988.21943},
      ZBLNUMBER = {0649.20002},
     }
  • [MR894827] Go to document L. Babai and &. Seress, "On the degree of transitivity of permutation groups: A short proof," J. Combin. Theory Ser. A, vol. 45, iss. 2, pp. 310-315, 1987.
    @article {MR894827, MRKEY = {894827},
      AUTHOR = {Babai, L{á}szl{ó} and Seress, {Á}kos},
      TITLE = {On the degree of transitivity of permutation groups: {A} short proof},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {45},
      YEAR = {1987},
      NUMBER = {2},
      PAGES = {310--315},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {20B20},
      MRNUMBER = {894827},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.1016/0097-3165(87)90023-9},
      }
  • [BS88] Go to document L. Babai and &. Seress, "On the diameter of Cayley graphs of the symmetric group," J. Combin. Theory Ser. A, vol. 49, iss. 1, pp. 175-179, 1988.
    @article {BS88, MRKEY = {957215},
      AUTHOR = {Babai, L{á}szl{ó} and Seress, {Á}kos},
      TITLE = {On the diameter of {C}ayley graphs of the symmetric group},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {49},
      YEAR = {1988},
      NUMBER = {1},
      PAGES = {175--179},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {05C25 (05C35)},
      MRNUMBER = {957215},
      MRREVIEWER = {Dave Witte Morris},
      DOI = {10.1016/0097-3165(88)90033-7},
      }
  • [7author] J. Bamberg, N. Gill, T. Hayes, H. A. Helfgott, G. Royle, Á. Seress, and P. Spiga, Bounds on the diameter of Cayley graphs of the symmetric group, 2012.
    @misc{7author,
      author = {J. Bamberg and N. Gill and T. Hayes and H. A. Helfgott and G. Royle and Á. Seress and P. Spiga},
      TITLE = {Bounds on the diameter of {C}ayley graphs of the symmetric group},
      NOTE = {to appear in {\em J. of Alg. Combin.}},
      ARXIV={1205.1596},
      YEAR={2012},
     }
  • [BS92] Go to document L. Babai and &. Seress, "On the diameter of permutation groups," European J. Combin., vol. 13, iss. 4, pp. 231-243, 1992.
    @article {BS92, MRKEY = {1179520},
      AUTHOR = {Babai, L{á}szl{ó} and Seress, {Á}kos},
      TITLE = {On the diameter of permutation groups},
      JOURNAL = {European J. Combin.},
      FJOURNAL = {European Journal of Combinatorics},
      VOLUME = {13},
      YEAR = {1992},
      NUMBER = {4},
      PAGES = {231--243},
      ISSN = {0195-6698},
      MRCLASS = {20B05 (20F05)},
      MRNUMBER = {1179520},
      MRREVIEWER = {Alberto Delgado},
      DOI = {10.1016/S0195-6698(05)80029-0},
      ZBLNUMBER = {0783.20001},
     }
  • [Boch89] Go to document A. Bochert, "Ueber die Zahl der verschiedenen Werthe, die eine Function gegebener Buchstaben durch Vertauschung derselben erlangen kann," Math. Ann., vol. 33, iss. 4, pp. 584-590, 1889.
    @article {Boch89, MRKEY = {1510562},
      AUTHOR = {Bochert, Alfred},
      TITLE = {Ueber die {Z}ahl der verschiedenen {W}erthe, die eine {F}unction gegebener {B}uchstaben durch {V}ertauschung derselben erlangen kann},
      JOURNAL = {Math. Ann.},
      FJOURNAL = {Mathematische Annalen},
      VOLUME = {33},
      YEAR = {1889},
      NUMBER = {4},
      PAGES = {584--590},
      ISSN = {0025-5831},
      CODEN = {MAANA},
      MRCLASS = {Contributed Item},
      MRNUMBER = {1510562},
      DOI = {10.1007/BF01444035},
      }
  • [BGSU2] Go to document J. Bourgain and A. Gamburd, "On the spectral gap for finitely-generated subgroups of $ SU(2)$," Invent. Math., vol. 171, iss. 1, pp. 83-121, 2008.
    @article {BGSU2, MRKEY = {2358056},
      AUTHOR = {Bourgain, Jean and Gamburd, Alex},
      TITLE = {On the spectral gap for finitely-generated subgroups of {$\rm SU(2)$}},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {171},
      YEAR = {2008},
      NUMBER = {1},
      PAGES = {83--121},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {22E30 (11B75 43A75)},
      MRNUMBER = {2358056},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s00222-007-0072-z},
      ZBLNUMBER = {1135.22010},
     }
  • [MR2415383] Go to document J. Bourgain and A. Gamburd, "Uniform expansion bounds for Cayley graphs of ${ SL}_2(\mathbb{F}_p)$," Ann. of Math., vol. 167, iss. 2, pp. 625-642, 2008.
    @article {MR2415383, MRKEY = {2415383},
      AUTHOR = {Bourgain, Jean and Gamburd, Alex},
      TITLE = {Uniform expansion bounds for {C}ayley graphs of {${\rm SL}_2(\mathbb{F}_p)$}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {167},
      YEAR = {2008},
      NUMBER = {2},
      PAGES = {625--642},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20F65 (05C25 05E15 11B30 20G40)},
      MRNUMBER = {2415383},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.4007/annals.2008.167.625},
      ZBLNUMBER = {1216.20042},
     }
  • [MR2587341] Go to document J. Bourgain, A. Gamburd, and P. Sarnak, "Affine linear sieve, expanders, and sum-product," Invent. Math., vol. 179, iss. 3, pp. 559-644, 2010.
    @article {MR2587341, MRKEY = {2587341},
      AUTHOR = {Bourgain, Jean and Gamburd, Alex and Sarnak, Peter},
      TITLE = {Affine linear sieve, expanders, and sum-product},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {179},
      YEAR = {2010},
      NUMBER = {3},
      PAGES = {559--644},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {11B30 (11B13 11N35)},
      MRNUMBER = {2587341},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s00222-009-0225-3},
      ZBLNUMBER = {1239.11103},
     }
  • [BGSup] Go to document J. Bourgain, A. Gamburd, and P. Sarnak, "Generalization of Selberg’s $\frac{3}{16}$ theorem and affine sieve," Acta Math., vol. 207, iss. 2, pp. 255-290, 2011.
    @article {BGSup, MRKEY = {2892611},
      AUTHOR = {Bourgain, Jean and Gamburd, Alex and Sarnak, Peter},
      TITLE = {Generalization of {S}elberg's {$\frac{3}{16}$} theorem and affine sieve},
      JOURNAL = {Acta Math.},
      FJOURNAL = {Acta Mathematica},
      VOLUME = {207},
      YEAR = {2011},
      NUMBER = {2},
      PAGES = {255--290},
      ISSN = {0001-5962},
      CODEN = {ACMAA8},
      MRCLASS = {11F72 (11N36)},
      MRNUMBER = {2892611},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s11511-012-0070-x},
      ZBLNUMBER = {06032745},
     }
  • [BGT] Go to document E. Breuillard, B. Green, and T. Tao, "Approximate subgroups of linear groups," Geom. Funct. Anal., vol. 21, iss. 4, pp. 774-819, 2011.
    @article {BGT, MRKEY = {2827010},
      AUTHOR = {Breuillard, Emmanuel and Green, Ben and Tao, Terence},
      TITLE = {Approximate subgroups of linear groups},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {21},
      YEAR = {2011},
      NUMBER = {4},
      PAGES = {774--819},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {20H30 (20G40)},
      MRNUMBER = {2827010},
      MRREVIEWER = {Herbert Abels},
      DOI = {10.1007/s00039-011-0122-y},
      ZBLNUMBER = {1229.20045},
     }
  • [MR1245303] Go to document P. Diaconis and L. Saloff-Coste, "Comparison techniques for random walk on finite groups," Ann. Probab., vol. 21, iss. 4, pp. 2131-2156, 1993.
    @article {MR1245303, MRKEY = {1245303},
      AUTHOR = {Diaconis, Persi and Saloff-Coste, Laurent},
      TITLE = {Comparison techniques for random walk on finite groups},
      JOURNAL = {Ann. Probab.},
      FJOURNAL = {The Annals of Probability},
      VOLUME = {21},
      YEAR = {1993},
      NUMBER = {4},
      PAGES = {2131--2156},
      ISSN = {0091-1798},
      CODEN = {APBYAE},
      MRCLASS = {60B15 (60J15)},
      MRNUMBER = {1245303},
      MRREVIEWER = {David J. Aldous},
      DOI = {10.1214/aop/1176989013},
      ZBLNUMBER = {0790.60011},
     }
  • [Din] Go to document O. Dinai, "Growth in ${ SL}_2$ over finite fields," J. Group Theory, vol. 14, iss. 2, pp. 273-297, 2011.
    @article {Din, MRKEY = {2788087},
      AUTHOR = {Dinai, Oren},
      TITLE = {Growth in {${\rm SL}\sb 2$} over finite fields},
      JOURNAL = {J. Group Theory},
      FJOURNAL = {Journal of Group Theory},
      VOLUME = {14},
      YEAR = {2011},
      NUMBER = {2},
      PAGES = {273--297},
      ISSN = {1433-5883},
      CODEN = {JGTHFQ},
      MRCLASS = {20G40 (05C25 11B30 20D60)},
      MRNUMBER = {2788087},
      MRREVIEWER = {Nick Gill},
      DOI = {10.1515/JGT.2010.056},
      ZBLNUMBER = {1236.20052},
     }
  • [DM] Go to document J. D. Dixon and B. Mortimer, Permutation Groups, New York: Springer-Verlag, 1996, vol. 163.
    @book {DM, MRKEY = {1409812},
      AUTHOR = {Dixon, John D. and Mortimer, Brian},
      TITLE = {Permutation Groups},
      SERIES = {Grad. Texts in Math.},
      VOLUME = {163},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1996},
      PAGES = {xii+346},
      ISBN = {0-387-94599-7},
      MRCLASS = {20B05 (20-01 20B07)},
      MRNUMBER = {1409812},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.1007/978-1-4612-0731-3},
      ZBLNUMBER = {0951.20001},
     }
  • [MR0573021] M. Fiedler, "Bounds for eigenvalues of doubly stochastic matrices," Linear Algebra and Appl., vol. 5, pp. 299-310, 1972.
    @article {MR0573021, MRKEY = {0573021},
      AUTHOR = {Fiedler, Miroslav},
      TITLE = {Bounds for eigenvalues of doubly stochastic matrices},
      JOURNAL = {Linear Algebra and Appl.},
      VOLUME = {5},
      YEAR = {1972},
      PAGES = {299--310},
      MRCLASS = {15A51 (15A18)},
      MRNUMBER = {0573021},
      ZBLNUMBER = {0264.15004},
     }
  • [Gangthe] Go to document A. R. Gangolli, Convergence bounds for Markov chains and applications to sampling, ProQuest LLC, Ann Arbor, MI, 1991.
    @book {Gangthe, MRKEY = {2686879},
      AUTHOR = {Gangolli, Anil Ramesh},
      TITLE = {Convergence bounds for {M}arkov chains and applications to sampling},
      NOTE = {Ph.D. thesis, Stanford University},
      PUBLISHER = {ProQuest LLC, Ann Arbor, MI},
      YEAR = {1991},
      PAGES = {152},
      MRCLASS = {Thesis},
      MRNUMBER = {2686879},
      URL = {http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:9205635},
      }
  • [GH2] N. Gill and H. A. Helfgott, Growth in solvable subgroups of ${\mathrm{GL}}_r(\mathbb{Z}/p\mathbb{Z})$, 2010.
    @misc{GH2,
      author = {Gill, Nick and Helfgott, Harald Andr{é}s},
      TITLE = {Growth in solvable subgroups of {${\mathrm{GL}}_r(\mathbb{Z}/p\mathbb{Z})$}},
      NOTE = {to appear in {\em Math. Annalen}},
      ARXIV={1008.5264},
      YEAR={2010},
      }
  • [GH1] N. Gill and H. A. Helfgott, "Growth of small generating sets in ${ SL}_n(\Bbb Z/p\Bbb Z)$," Int. Math. Res. Not., vol. 2011, iss. 18, p. no. 18, 4226-4251.
    @article {GH1, MRKEY = {2836020},
      AUTHOR = {Gill, Nick and Helfgott, Harald Andr{é}s},
      TITLE = {Growth of small generating sets in {${\rm SL}\sb n(\Bbb Z/p\Bbb Z)$}},
      JOURNAL = {Int. Math. Res. Not.},
      FJOURNAL = {International Mathematics Research Notices. IMRN},
      SORTYEAR = {2011},
      NUMBER = {18},
      PAGES = {No.~18, 4226--4251},
      ISSN = {1073-7928},
      MRCLASS = {11B30 (20D60 20G40)},
      MRNUMBER = {2836020},
      MRREVIEWER = {Martin W. Liebeck},
      VOLUME = {2011},
      ZBLNUMBER = {1234.20059},
     }
  • [SGV] Go to document S. A. Golsefidy and P. P. Varjú, "Expansion in perfect groups," Geom. Funct. Anal., vol. 22, iss. 6, pp. 1832-1891, 2012.
    @article {SGV, MRKEY = {3000503},
      AUTHOR = {Golsefidy, A. Salehi and Varj{ú},
      P{é}ter P.},
      TITLE = {Expansion in perfect groups},
      JOURNAL = {Geom. Funct. Anal.},
      FJOURNAL = {Geometric and Functional Analysis},
      VOLUME = {22},
      YEAR = {2012},
      NUMBER = {6},
      PAGES = {1832--1891},
      ISSN = {1016-443X},
      CODEN = {GFANFB},
      MRCLASS = {20F65 (05C25)},
      MRNUMBER = {3000503},
      DOI = {10.1007/s00039-012-0190-7},
      ZBLNUMBER = {06132223},
     }
  • [Hel08] Go to document H. A. Helfgott, "Growth and generation in ${ SL}_2(\Bbb Z/p\Bbb Z)$," Ann. of Math., vol. 167, iss. 2, pp. 601-623, 2008.
    @article {Hel08, MRKEY = {2415382},
      AUTHOR = {Helfgott, H. A.},
      TITLE = {Growth and generation in {${\rm SL}\sb 2(\Bbb Z/p\Bbb Z)$}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {167},
      YEAR = {2008},
      NUMBER = {2},
      PAGES = {601--623},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20G40 (05C25 20F69)},
      MRNUMBER = {2415382},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.4007/annals.2008.167.601},
      ZBLNUMBER = {1213.20045},
     }
  • [HeSL3] Go to document H. A. Helfgott, "Growth in ${ SL}_3(\Bbb Z/p\Bbb Z)$," J. Eur. Math. Soc. $($JEMS$)$, vol. 13, iss. 3, pp. 761-851, 2011.
    @article {HeSL3, MRKEY = {2781932},
      AUTHOR = {Helfgott, H. A.},
      TITLE = {Growth in {${\rm SL}\sb 3(\Bbb Z/p\Bbb Z)$}},
      JOURNAL = {J. Eur. Math. Soc. $($JEMS$)$},
      FJOURNAL = {Journal of the European Mathematical Society (JEMS)},
      VOLUME = {13},
      YEAR = {2011},
      NUMBER = {3},
      PAGES = {761--851},
      ISSN = {1435-9855},
      MRCLASS = {20G40 (05C25 11B75 20D60 20F65)},
      MRNUMBER = {2781932},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.4171/JEMS/267},
      ZBLNUMBER = {1235.20047},
     }
  • [HLW] Go to document S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bull. Amer. Math. Soc., vol. 43, iss. 4, pp. 439-561, 2006.
    @article {HLW, MRKEY = {2247919},
      AUTHOR = {Hoory, Shlomo and Linial, Nathan and Wigderson, Avi},
      TITLE = {Expander graphs and their applications},
      JOURNAL = {Bull. Amer. Math. Soc.},
      FJOURNAL = {American Mathematical Society. Bulletin. New Series},
      VOLUME = {43},
      YEAR = {2006},
      NUMBER = {4},
      PAGES = {439--561},
      ISSN = {0273-0979},
      CODEN = {BAMOAD},
      MRCLASS = {68Q15 (00-02 05C25 05C80 60G50 68Q17 68R10)},
      MRNUMBER = {2247919},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1090/S0273-0979-06-01126-8},
      ZBLNUMBER = {1147.68608},
     }
  • [Hrushovski] Go to document E. Hrushovski, "Stable group theory and approximate subgroups," J. Amer. Math. Soc., vol. 25, iss. 1, pp. 189-243, 2012.
    @article {Hrushovski, MRKEY = {2833482},
      AUTHOR = {Hrushovski, Ehud},
      TITLE = {Stable group theory and approximate subgroups},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {25},
      YEAR = {2012},
      NUMBER = {1},
      PAGES = {189--243},
      ISSN = {0894-0347},
      MRCLASS = {03C45 (11P70)},
      MRNUMBER = {2833482},
      MRREVIEWER = {Katrin U. Tent},
      DOI = {10.1090/S0894-0347-2011-00708-X},
      ZBLNUMBER = {1259.03049},
     }
  • [Jor] C. Jordan, Traité des Substitutions et des Équations Algébriques, Paris: Librairie Scientifique et Technique A. Blanchard, 1957.
    @book {Jor, MRKEY = {0091260},
      AUTHOR = {Jordan, Camille},
      TITLE = {Traité des Substitutions et des Équations Algébriques},
      PUBLISHER = {Librairie Scientifique et Technique A. Blanchard},
      ADDRESS={Paris},
      YEAR = {1957},
      PAGES = {xviii+667},
      MRCLASS = {15.0X},
      MRNUMBER = {0091260},
      ZBLNUMBER = {0078.01204},
     }
  • [KMS84] Go to document D. Kornhauser, G. Miller, and P. Spirakis, "Coordinating pebble motion on graphs, the diameter of permutation groups, and applications," in Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, Singer Island, FL, 1984, pp. 241-250.
    @inproceedings{KMS84,
      author = {D. Kornhauser and G. Miller and P. Spirakis},
      TITLE = {Coordinating pebble motion on graphs, the diameter of permutation groups, and applications},
      BOOKTITLE = {Proceedings of the 25th IEEE Symposium on Foundations of Computer Science},
      PAGES = {241--250},
      PUBLISHER = {IEEE Computer Society Press},
      ADDRESS ={Singer Island, FL},
      YEAR = {1984},
      DOI = {10.1109/SFCS.1984.715921},
     }
  • [LP] Go to document M. J. Larsen and R. Pink, "Finite subgroups of algebraic groups," J. Amer. Math. Soc., vol. 24, iss. 4, pp. 1105-1158, 2011.
    @article {LP, MRKEY = {2813339},
      AUTHOR = {Larsen, Michael J. and Pink, Richard},
      TITLE = {Finite subgroups of algebraic groups},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {24},
      YEAR = {2011},
      NUMBER = {4},
      PAGES = {1105--1158},
      ISSN = {0894-0347},
      MRCLASS = {20H20 (20G20)},
      MRNUMBER = {2813339},
      MRREVIEWER = {Peter A. Brooksbank},
      DOI = {10.1090/S0894-0347-2011-00695-4},
      ZBLNUMBER = {1241.20054},
     }
  • [MR703984] Go to document M. W. Liebeck, "On graphs whose full automorphism group is an alternating group or a finite classical group," Proc. London Math. Soc., vol. 47, iss. 2, pp. 337-362, 1983.
    @article {MR703984, MRKEY = {0703984},
      AUTHOR = {Liebeck, Martin W.},
      TITLE = {On graphs whose full automorphism group is an alternating group or a finite classical group},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
      VOLUME = {47},
      YEAR = {1983},
      NUMBER = {2},
      PAGES = {337--362},
      ISSN = {0024-6115},
      CODEN = {PLMTAL},
      MRCLASS = {05C25 (20B25)},
      MRNUMBER = {0703984},
      MRREVIEWER = {W. M. Kantor},
      DOI = {10.1112/plms/s3-47.2.337},
      ZBLNUMBER = {0517.05037},
     }
  • [MR1395866] L. Lovász, "Random walks on graphs: a survey," in Combinatorics, Paul Erdős is Eighty, Vol. 2, Budapest: János Bolyai Math. Soc., 1996, vol. 2, pp. 353-397.
    @incollection {MR1395866, MRKEY = {1395866},
      AUTHOR = {Lov{á}sz, L.},
      TITLE = {Random walks on graphs: a survey},
      BOOKTITLE = {Combinatorics, {P}aul {E}rdős is Eighty, {V}ol. 2},
      VENUE={{K}eszthely, 1993},
      SERIES = {Bolyai Soc. Math. Stud.},
      VOLUME = {2},
      PAGES = {353--397},
      PUBLISHER = {János Bolyai Math. Soc.},
      ADDRESS = {Budapest},
      YEAR = {1996},
      MRCLASS = {60J15 (05C50 05C99)},
      MRNUMBER = {1395866},
      ZBLNUMBER = {0854.60071},
     }
  • [MR0465509] F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes., Amsterdam: North-Holland Publishing Co., 1977.
    @book {MR0465509, MRKEY={0465509},
      AUTHOR = {MacWilliams, F. J. and Sloane, N. J. A.},
      TITLE = {The theory of error-correcting codes.},
      NOTE = {North-Holland Mathematical Library, Vol. 16},
      PUBLISHER = {North-Holland Publishing Co.},
      ADDRESS = {Amsterdam},
      YEAR = {1977},
      MRCLASS = {94A10},
      MRNUMBER = {0465509},
      MRREVIEWER = {Ian Blake},
      ZBLNUMBER = {0369.94008},
     }
  • [McK] Go to document P. McKenzie, "Permutations of bounded degree generate groups of polynomial diameter," Inform. Process. Lett., vol. 19, iss. 5, pp. 253-254, 1984.
    @article {McK, MRKEY = {0777808},
      AUTHOR = {McKenzie, Pierre},
      TITLE = {Permutations of bounded degree generate groups of polynomial diameter},
      JOURNAL = {Inform. Process. Lett.},
      FJOURNAL = {Information Processing Letters},
      VOLUME = {19},
      YEAR = {1984},
      NUMBER = {5},
      PAGES = {253--254},
      ISSN = {0020-0190},
      CODEN = {IFPLAT},
      MRCLASS = {68Q25 (20B99 68Q40 68R05)},
      MRNUMBER = {0777808},
      DOI = {10.1016/0020-0190(84)90062-0},
      ZBLNUMBER = {0569.68031},
     }
  • [Mohtech] Go to document B. Mohar, "Eigenvalues, diameter, and mean distance in graphs," Graphs Combin., vol. 7, iss. 1, pp. 53-64, 1991.
    @article {Mohtech, MRKEY = {1105467},
      AUTHOR = {Mohar, Bojan},
      TITLE = {Eigenvalues, diameter, and mean distance in graphs},
      JOURNAL = {Graphs Combin.},
      FJOURNAL = {Graphs and Combinatorics},
      VOLUME = {7},
      YEAR = {1991},
      NUMBER = {1},
      PAGES = {53--64},
      ISSN = {0911-0119},
      CODEN = {GRCOE5},
      MRCLASS = {05C50 (05C40 15A42)},
      MRNUMBER = {1105467},
      MRREVIEWER = {Ernie S. Solheid},
      DOI = {10.1007/BF01789463},
      ZBLNUMBER = {0771.05063},
     }
  • [Paktalk] Go to document I. Pak, Problems: new, old and unusual.
    @misc{Paktalk,
      author = {I. Pak},
      TITLE = {Problems: new, old and unusual},
      NOTE = {talk at {N}ational {U}niversity of {I}reland, {G}alway, {I}reland, {D}ec 1, 2009},
      URL={http://larmor.nuigalway.ie/~detinko/Igor.pdf},
      }
  • [MR2898694] Go to document C. E. Praeger, L. Pyber, P. Spiga, and E. Szabó, "Graphs with automorphism groups admitting composition factors of bounded rank," Proc. Amer. Math. Soc., vol. 140, iss. 7, pp. 2307-2318, 2012.
    @article {MR2898694, MRKEY = {2898694},
      AUTHOR = {Praeger, Cheryl E. and Pyber, Laszl{ó} and Spiga, Pablo and Szab{ó},
      Endre},
      TITLE = {Graphs with automorphism groups admitting composition factors of bounded rank},
      JOURNAL = {Proc. Amer. Math. Soc.},
      FJOURNAL = {Proceedings of the American Mathematical Society},
      VOLUME = {140},
      YEAR = {2012},
      NUMBER = {7},
      PAGES = {2307--2318},
      ISSN = {0002-9939},
      CODEN = {PAMYAR},
      MRCLASS = {05C25 (20B25)},
      MRNUMBER = {2898694},
      DOI = {10.1090/S0002-9939-2011-11100-6},
      }
  • [MR576980] Go to document C. E. Praeger and J. Saxl, "On the orders of primitive permutation groups," Bull. London Math. Soc., vol. 12, iss. 4, pp. 303-307, 1980.
    @article {MR576980, MRKEY = {0576980},
      AUTHOR = {Praeger, Cheryl E. and Saxl, Jan},
      TITLE = {On the orders of primitive permutation groups},
      JOURNAL = {Bull. London Math. Soc.},
      FJOURNAL = {The Bulletin of the London Mathematical Society},
      VOLUME = {12},
      YEAR = {1980},
      NUMBER = {4},
      PAGES = {303--307},
      ISSN = {0024-6093},
      CODEN = {LMSBBT},
      MRCLASS = {20B20},
      MRNUMBER = {0576980},
      MRREVIEWER = {Peter Rowlinson},
      DOI = {10.1112/blms/12.4.303},
      }
  • [Pyb93] Go to document L. Pyber, "On the orders of doubly transitive permutation groups, elementary estimates," J. Combin. Theory Ser. A, vol. 62, iss. 2, pp. 361-366, 1993.
    @article {Pyb93, MRKEY = {1207742},
      AUTHOR = {Pyber, L.},
      TITLE = {On the orders of doubly transitive permutation groups, elementary estimates},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {62},
      YEAR = {1993},
      NUMBER = {2},
      PAGES = {361--366},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {20B20},
      MRNUMBER = {1207742},
      MRREVIEWER = {Cheryl E. Praeger},
      DOI = {10.1016/0097-3165(93)90053-B},
      ZBLNUMBER = {0781.20002},
     }
  • [PS] L. Pyber and E. Szabó, Growth in finite simple groups of Lie type of bounded rank, 2010.
    @misc{PS,
      author={Pyber, L. and Szab{ó},
      E.},
      TITLE={Growth in finite simple groups of {L}ie type of bounded rank},
      YEAR={2010},
      NOTE={submitted},
      ARXIV={1005.1881},
     }
  • [MR810596] I. Z. Ruzsa and S. Turjányi, "A note on additive bases of integers," Publ. Math. Debrecen, vol. 32, iss. 1-2, pp. 101-104, 1985.
    @article {MR810596, MRKEY = {0810596},
      AUTHOR = {Ruzsa, I. Z. and Turj{á}nyi, S.},
      TITLE = {A note on additive bases of integers},
      JOURNAL = {Publ. Math. Debrecen},
      FJOURNAL = {Publicationes Mathematicae Debrecen},
      VOLUME = {32},
      YEAR = {1985},
      NUMBER = {1-2},
      PAGES = {101--104},
      ISSN = {0033-3883},
      CODEN = {PUMAAR},
      MRCLASS = {11B13},
      MRNUMBER = {0810596},
      MRREVIEWER = {Anne Ludington Young},
      ZBLNUMBER = {0588.10063},
     }
  • [MR1970241] Go to document &. Seress, Permutation Group Algorithms, Cambridge: Cambridge Univ. Press, 2003, vol. 152.
    @book {MR1970241, MRKEY = {1970241},
      AUTHOR = {Seress, {Á}kos},
      TITLE = {Permutation Group Algorithms},
      SERIES = {Cambridge Tracts in Math.},
      VOLUME = {152},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {2003},
      PAGES = {x+264},
      ISBN = {0-521-66103-X},
      MRCLASS = {20B40 (20-04)},
      MRNUMBER = {1970241},
      MRREVIEWER = {D. F. Holt},
      DOI = {10.1017/CBO9780511546549},
      ZBLNUMBER = {1028.20002},
     }
  • [MR0257203] C. C. Sims, "Computational methods in the study of permutation groups," in Computational Problems in Abstract Algebra (Proc., Oxford: Pergamon, 1970, pp. 169-183.
    @incollection {MR0257203, MRKEY = {0257203},
      AUTHOR = {Sims, Charles C.},
      TITLE = {Computational methods in the study of permutation groups},
      BOOKTITLE = {Computational {P}roblems in {A}bstract {A}lgebra ({P}roc.},
      VENUE={{C}onf., {O}xford, 1967},
      PAGES = {169--183},
      PUBLISHER = {Pergamon},
      ADDRESS = {Oxford},
      YEAR = {1970},
      MRCLASS = {20.20 (65.00)},
      MRNUMBER = {0257203},
      MRREVIEWER = {H. Kimura},
      ZBLNUMBER = {0449.20002},
     }
  • [Sim71] C. C. Sims, "Computation with permutation groups," in Proc. Second Symposium on Symbolic and Algebraic Maniupulation, New York: ACM, 1971, pp. 23-28.
    @incollection{Sim71,
      author = {Sims, Charles C.},
      TITLE = {Computation with permutation groups},
      BOOKTITLE = {Proc. {S}econd {S}ymposium on {S}ymbolic and {A}lgebraic {M}aniupulation},
      YEAR = {1971},
      PAGES = {23--28},
      PUBLISHER = {{A}{C}{M}},
      ADDRESS = {New York},
      }
  • [MR2155059] Go to document B. Sudakov, E. Szemerédi, and V. H. Vu, "On a question of Erdős and Moser," Duke Math. J., vol. 129, iss. 1, pp. 129-155, 2005.
    @article {MR2155059, MRKEY = {2155059},
      AUTHOR = {Sudakov, B. and Szemer{é}di, E. and Vu, V. H.},
      TITLE = {On a question of {E}rdős and {M}oser},
      JOURNAL = {Duke Math. J.},
      FJOURNAL = {Duke Mathematical Journal},
      VOLUME = {129},
      YEAR = {2005},
      NUMBER = {1},
      PAGES = {129--155},
      ISSN = {0012-7094},
      CODEN = {DUMJAO},
      MRCLASS = {11P70 (05D05 11B75)},
      MRNUMBER = {2155059},
      MRREVIEWER = {Mei Chu Chang},
      DOI = {10.1215/S0012-7094-04-12915-X},
      ZBLNUMBER = {1155.11346},
     }
  • [MR2501249] Go to document T. Tao, "Product set estimates for non-commutative groups," Combinatorica, vol. 28, iss. 5, pp. 547-594, 2008.
    @article {MR2501249, MRKEY = {2501249},
      AUTHOR = {Tao, Terence},
      TITLE = {Product set estimates for non-commutative groups},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {28},
      YEAR = {2008},
      NUMBER = {5},
      PAGES = {547--594},
      ISSN = {0209-9683},
      MRCLASS = {11B30 (11P70)},
      MRNUMBER = {2501249},
      MRREVIEWER = {Ben Joseph Green},
      DOI = {10.1007/s00493-008-2271-7},
      ZBLNUMBER = {1254.11017},
     }
  • [Var] Go to document P. P. Varjú, "Expansion in $SL_d(\mathcal{O}_K/I)$, $I$ square-free," J. Eur. Math. Soc. $($JEMS$)$, vol. 14, iss. 1, pp. 273-305, 2012.
    @article {Var, MRKEY = {2862040},
      AUTHOR = {Varj{ú},
      P{é}ter P.},
      TITLE = {Expansion in {$SL\sb d(\mathcal{O}\sb K/I)$},
      {$I$} square-free},
      JOURNAL = {J. Eur. Math. Soc. $($JEMS$)$},
      FJOURNAL = {Journal of the European Mathematical Society (JEMS)},
      VOLUME = {14},
      YEAR = {2012},
      NUMBER = {1},
      PAGES = {273--305},
      ISSN = {1435-9855},
      MRCLASS = {20F65 (05C25 11B30 11B75)},
      MRNUMBER = {2862040},
      MRREVIEWER = {Bijan Taeri},
      DOI = {10.4171/JEMS/302},
      ZBLNUMBER = {05995804},
     }
  • [MR0183775] H. Wielandt, Finite Permutation Groups, New York: Academic Press, 1964.
    @book {MR0183775, MRKEY = {0183775},
      AUTHOR = {Wielandt, Helmut},
      TITLE = {Finite Permutation Groups},
      NOTE={translated from the German by R. Bercov},
      PUBLISHER = {Academic Press},
      ADDRESS = {New York},
      YEAR = {1964},
      PAGES = {x+114},
      MRCLASS = {20.20},
      MRNUMBER = {0183775},
      MRREVIEWER = {N. Ito},
      ZBLNUMBER = {0138.02501},
     }

Authors

Harald A. Helfgott

École Normale Supérieure, Paris, France

Ákos Seress

The University of Western Australia, Crawley, Australia and The Ohio State University, Columbus, OH