On Thu, 7 May 2015 07:55:23 -0400, Andy Latto <andy.latto@pobox.com> wrote:

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?

My understanding of the definition of graph diameter is that is is one greater than the max distance between nodes, so that the diameter of an empty graph is 0, and the diameter of a single node graph is 1.

(obviously, the distance between 2

...

single-cycle derangements will be N).

That's a typo, the distance is N-1.

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.

I meant two derangements relative to one another, not to the "original" position.

...

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.

The ceiling(log_2(n)) estimate seems intuitively right, as it takes at most that number of bit swaps to reverse a word, but the observation is wrong. When doing a reversal, all pairwise distances are different, therefore the first swap can send no more than 2 objects to the right place. We win only by incremental adjustments. And still, it is not obvious that an arbitrary permutation will be decomposable as easily as the reversal. Leo