On the diameter of permutation groups

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 such that every element of G can be expressed as a word of length at most in AUA(-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, root n log n. We give a quasipolynomial upper bound, namely, diam(G) = exp (O((log n)(4) log log n)) = exp ((log log vertical bar G vertical bar)(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 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.