Computing short generator sequences (Q1090414): Difference between revisions

Let P be a finite set of permutations of n letters. The diameter of the permutation group \(G=<P>\) (with respect to P) is by definition the least integer k such that every permutation in G can be expressed as a product of at most k elements of P. This concept corresponds to the diameter of the Cayley graph associated to the given presentation of G. It is shown in the paper that the diameter of a permutation group G generated by a set P of cycles of bounded degree is \(O(n^ 2)\). This bound is best possible. In addition, it is shown that such short products can be found in polynomial time. The techniques presented in the paper may be applied to various well known permutation-group puzzles.