On Wed, May 6, 2015 at 10:51 PM, Leo Broukhis <leob@mailcom.com> wrote:
The graph of permutations of N elements with edges corresponding to transpositions has diameter N
I think the diameter is N-1. Given two permutations X and Y, we can find k transpositions T1, T2,...Tk such that XT1T2...Tk agrees with Y on k of the objects being permuted. But when k = N-1, if n of the elements go to the right place, the last one must, too; where else could it go? (obviously, the distance between 2
single-cycle derangements will be N).
This seems completely wrong. 1->2->3->.....100->1, and 1->3->2->4->5....->100->1 are single cycle derangements, and they are adjacent in the graph.
What if we allow combining disjoint same distance transpositions, e.g.
1234567890 <-> 3412765098
That reduces the diameter to ceiling(log_2(n)); we can find a permutation of this form that sends half of the objects being permuted to the right place, then multiply by another that fixes these and sends half of the remainder to the right place, and so forth. Andy