Name
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))). |
Year | DOI | Venue |
|---|---|---|
2004 | 10.5555/982792.982956 | SODA |
Keywords | Field | DocType |
word length,n ln n,polynomial bound,las vegas polynomial time,polynomially bounded word length,n log n,element order bottleneck,maximum required word length,markov chain,symmetric group,polynomial time | Alternating polynomial,Discrete mathematics,Combinatorics,Symmetric group,Polynomial,Permutation,Markov chain,Symmetric polynomial,Conjecture,Mathematics,Bounded function | Conference |
ISBN | Citations | PageRank |
0-89871-558-X | 6 | 0.55 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laszlo Babai | 1 | 3537 | 573.58 |
| Robert Beals | 2 | 442 | 35.78 |
| Ákos Seress | 3 | 218 | 36.22 |