On the diameter of the symmetric group: Polynomial bounds

László Babai, Robert Beals, Ákos Seress

Research output: Contribution to conferencePaperpeer-review

20 Scopus citations

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 average-case 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))).

Original languageEnglish (US)
Pages1101-1105
Number of pages5
StatePublished - 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'On the diameter of the symmetric group: Polynomial bounds'. Together they form a unique fingerprint.

Cite this