LB's question: 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? ... At what point the diameter will be O(sqrt(N)), O(log(N))? Less than O(log(N))? --ANSWER: SInce there are N! permutations, if we allow 1-step rotations (2 choices) the diameter necessarily is >=log2(N!) which is about N*lg(N). Actually diam=infinity since you can only access the cyclic subgroup, but I'm trying to illustrate a very simple bounding technique here. If we allow any-#step-rotations, there are N choices, hence diam>=log(N!)/log(N) which is about N. If we allow 2-element swaps, LB showed diam=N. If we allow swapping only a FIXED element (eg, the first) with an arbitrary one, there are N-1 choices, hence diam>=log(N!)/log(N-1) which is about N. This is in fact the correct order of magnitude since I can build one of LB's transpositions from a constant number of mine.