On the diameter of permutation groups

Given a finite group $G$ and a set $A$ of generators, the diameter diam$(\mathrm{\Gamma }(G,A))$ of the Cayley graph $\mathrm{\Gamma }(G,A)$ is the smallest $\mathrm{\ell }$ such that every element of $G$ can be expressed as a word of length at most $\mathrm{\ell }$ in $A\cup A^{-1}$. We are concerned with bounding diam(G):= ${\max }_A$ diam$(\mathrm{\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 \mathrm{\mid }G\mathrm{\mid }{)}^{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$.