On the diameter of permutation groups

Abstract

Given a finite group $G$ and a set $A$ of generators, the diameter 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 diam(G):= ${\max }_A$ 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, \[\text{diam}(G) = \exp(O((\log n)^4 \log\log n)) = \exp((\log \log |G|)^{O(1)})\] for G = Sym(n) or G = \Alt(n), where the implied constants are absolute. This addresses a key open case of Babai's conjecture on diameters of simple groups. By standard results, our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree $n$.

42 pages. Minimal additions. Last version, to appear in Ann. of Math

References in corpus (2)

• Expansion in $S{L}_d(O_K/I)$, $I$ square-free
• Growth in solvable subgroups of GL_r(Z/pZ)

Cited by in corpus (2)

• Expansion in finite simple groups of Lie type
• Uniform Diameter Bounds in Branch Groups