The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the diameter of this graph is known.

A computer simulation gives the conjecture that the diameter is $\lfloor n^2/4 \rfloor$. In (Heydemann, "Cayley graphs and interconnection networks", in Graph Symmetry: Algebraic Methods and Applications, Eds. Hahn and Sabidussi), it is stated in p. 213 that the diameter of the modified bubble-sort graph is $\lfloor n^2/4 \rfloor$, and the result is attributed to (J.-F. Sacle,"Diameter of some Cayley graphs", private communication, 1997). However, I couldn't find any proof of this result. Is any proof for this formula given in the literature?

This problem was studied earlier in a paper of Jerrum's ("The complexity of finding minimum-length generator sequences, TCS, 1985), but no closed-form expression for the diameter is given there either.

  • $\begingroup$ You might be able to show by induction that the permutation (1,n/2)(2,n/2+1)...(n/2-1,n) or something similar is at near maximal distance in the graph from the identity. Even if not, constructing parts of the graph for n up to 5 should give some more clues. Gerhard "Examine The Output More Closely" Paseman, 2015.08.08 $\endgroup$ – Gerhard Paseman Aug 9 '15 at 4:48
  • $\begingroup$ You can show that a typical permutation is of distance at least $cn^2$ from the identity by considering the average of the number of inversions of $(1 2 ... n)^k$ times the permutation. However, this leads to the wrong constant. $\endgroup$ – Douglas Zare Aug 10 '15 at 3:40
  • $\begingroup$ You could try the old-fashioned way of emailing Jean-François Saclé and asking him about the privately communicated proof. His email address is on some recent papers that are online. $\endgroup$ – Gordon Royle Aug 10 '15 at 13:34
  • $\begingroup$ The email sacle@lri.fr that I found on a recent paper bounced back. $\endgroup$ – Ashwin Ganesan Aug 16 '15 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.