[math-fun] Sizing permutation graphs
The graph of permutations of N elements with edges corresponding to transpositions has diameter N (obviously, the distance between 2 single-cycle derangements will be N). What happens to the diameter if we add edges corresponding to 1-step rotations (considering both unidirectional, e.g. rotating only to the right, and bidirectional edges)? What if we allow arbitrary rotations? What if we allow combining disjoint same distance transpositions, e.g. 1234567890 <-> 3412765098 For bit vectors, the operation can be described as swapbits(bitvec, mask, distance) { assert (((mask << distance) & mask) == 0); temp = ((bitvec>>distance) ^ value) & mask; return bitvec ^ temp ^ (temp<<distance); } At what point the diameter will be O(sqrt(N)), O(log(N))? Less than O(log(N))? Has this been studied before? Thanks, Leo
This may be of interest: Diameter of the Symmetric Group, Polynomial Bounds <http://people.cs.uchicago.edu/~laci/papers/04soda.diam.pdf> And see the references for other papers on this topic. 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 (obviously, the distance between 2 single-cycle derangements will be N).
What happens to the diameter if we add edges corresponding to 1-step rotations (considering both unidirectional, e.g. rotating only to the right, and bidirectional edges)?
What if we allow arbitrary rotations?
What if we allow combining disjoint same distance transpositions, e.g.
1234567890 <-> 3412765098
For bit vectors, the operation can be described as
swapbits(bitvec, mask, distance) { assert (((mask << distance) & mask) == 0); temp = ((bitvec>>distance) ^ value) & mask; return bitvec ^ temp ^ (temp<<distance); }
At what point the diameter will be O(sqrt(N)), O(log(N))? Less than O(log(N))?
Has this been studied before?
Thanks, Leo
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
participants (3)
-
Andy Latto -
Leo Broukhis -
W. Edwin Clark