On the diameter of the symmetric group: polynomial bounds

Abstract We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group. The best available bound on the maximum required word length is exponential in √ n log n. Polynomial bounds on the word length have previously been established for very special classes of generating sets only. In this paper we give a polynomial bound on the word length under the sole condition that one of the generators fix at least 67% of the domain. Words of the length claimed can be found in Las Vegas polynomial time. The proof involves a Markov chain mixing estimate which permits us, apparently for the first time, to break the "element order bottleneck." As a corollary, we obtain the following averagecase result: for a 1 − δ fraction of the pairs of generators for the symmetric group, the word length is polynomially bounded. It is known that for almost all pairs of generators, the word length is less than exp( √ n ln n(1 + o(1)))