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