9
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Aug 9, 2015 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$ Aug 10, 2015 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$ Aug 10, 2015 at 13:34
  • $\begingroup$ The email [email protected] that I found on a recent paper bounced back. $\endgroup$ Aug 16, 2015 at 14:37

1 Answer 1

3
$\begingroup$

The claim seems to be correct, here's an argument.

For all $n$, the diameter of the modified bubble sort graph is $\lfloor n/4 \rfloor$. One element with this word norm is $\pi(i) = i+\lfloor n/2 \rfloor$ (addition modulo $n$).

First, consider even $n = 2k$, so $\lfloor n^2/4 \rfloor = k^2$.

First, the lower bound.

Let our set to permute be $N = \mathbb{Z}/\mathbb{Z}_n$ which I mostly biject with $\{0,1,...,n-1\}$, and for the mental picture it is useful to think it's laid out on a circle. Define the huskiness of $\pi \in S_n$ to be $h(\pi) = \sum_{i \in N} |i - \pi(i)|'$ where $|a|' = \min \{|b| \;|\; b \in \mathbb{Z}, a = b + n\mathbb{Z}\}$ for $a \in N$. In other words this is just the sum of distances from $i$ to $\pi(i)$ over $n \in N$, in the cyclic graph structure of $N$. Clearly huskiness is $0$ iff the permutation is trivial.

Now, $S_n$ acts on itself by precomposition, and in this action the modified bubble sort generators decrease huskiness by at most $2$, since you move at most two elements of $N$, each by at most a distance of one. The permutation $\pi(i) = i+k$ has huskiness $h(\pi) = n k$, so you cannot generate $\pi$ with less than $nk/2 = 2k^2/2 = k^2$ generators, giving the desired lower bound.

A possibly helpful note if you have some chirality confusion (or in case I do): Note that precomposition basically corresponds to thinking of $\pi(i)$ as the "goal" for $i$, and when you precompose by a swap involving $i$, you can think of $i$ as moving. (Postcomposition moves the goalposts.) I recommend thinking of the permutation $\pi$ as an arrangement of the values $N$ on $N$ where the value at $i$ is initially $\pi(i)$. The precomposition action moves these numbers around, and our goal is to move the value $\pi(i)$ to $\pi(i)$ for all $i \in N$.

Second, then the upper bound.

We show the stronger fact that the diameter is $k^2$ even if you drop the generator $(0, n-1)$. For the mental picture, it is useful to open up $N$ from a circle to a line. Define the friskiness of $\pi \in S_n$ to be $f(\pi) = \sum_{i \in N} d(i, \pi(i))$ where $d : N \times N \to \mathbb{N}$ is the graph metric in the linear graph structure of $N$, or the Euclidean metric on $\mathbb{R}$ applied to the representative in $\{0,1,...,n-1\}$.

The friskiness of a permutation is at most $2k^2$. Here's an argument for that, though I suppose there must be some easier way: Suppose $f(\pi)$ is maximal. I claim that we may assume $\pi(i) = n-1-i$, by sorting an arbitrary permutation into this $\pi$ without decreasing friskiness: to do this, bubble $0$ from $\pi(0)$ up to $n-1$ by pre-composing with swaps $(i, i+1)$, $i \neq n-1$, observing no individual step decreases friskiness. Thus, we may assume $\pi(0) = n-1$. But assuming $\pi(0) = n-1$, bubbling $1$ from $\pi(1)$ up to $n-2$ does not decrease friskiness: the first step may reduce the contribution of $1$ to friskiness if $\pi(1) = 0$, but the contribution of $\pi^{-1}(1)$ is increased, since $\pi^{-1}(1) \neq 0$ (unless $n = 2$, in which case we were done anyway). Continue inductively. It follows that indeed for $\pi(i) = n-i$ the friskiness $$ h(\pi) = \sum_{i = 0}^n d(i,n-1-i) = kn = 2k^2 $$ is the maximal possible.

(Not that it matters, but the sorting above is not bubble sort, it's basically selection sort but by swaps, which I suppose has no name.)

Friskiness is $0$ iff the permutation is trivial, so it is enough to show that we can always decrease the friskiness of a non-trivial permutation by $2$ by applying a swap at a suitable position. For this, simply swap (as always by precomposition) at any position where $\pi(i) > i$ and $\pi(i+1) < i+1$ (which you can find by looking at $i \in N$ in increasing order). This concludes the proof of the upper bound.

Second, consider odd $n = 2k+1$, so $\lfloor n^2/4 \rfloor = k^2+k$.

First, the upper bound.

This reduces directly to the previous case: take $2k \in N$, and move it to its final position, in at most $k$ steps. Now, by the upper bound from the even case (for the smaller set of generators), we can move all the $n-1 = 2k$ to their final places with $k^2$ swaps, giving the upper bound $k^2+k$ as required.

Second, the lower bound.

Huskiness is not a sufficient in variant in this case, as its maximal value is $k$ too small. We now define a more complex invariant called muskiness.

For each $i \in N$, define $v_i = \pi(i) - i$ if $\pi(i) - i \in [0,k]$ and $v_i = i - \pi(i)$ otherwise. This is the "vector field" that at $i \in N$ indicates the (unique) geodesic from $i$ to $\pi(i)$. We define the oriented duskiness of $\pi \in S_n$ to be $$ d(\pi) = \sum_{i \in N} v_i/n. $$ Define the unoriented duskiness of $\pi$ to be $|d(\pi)|$, and finally define its muskiness to be the sum of its huskiness (defined as in the even case) and unoriented duskiness, $m(\pi) = h(\pi) + |d(\pi)|$.

We again show that we cannot lower muskiness by more than $2$ by applying a generator $(i, i+1)$. There are a few cases to consider. The main technical issue when you swap is that when the distance from $i$ to $\pi(i)$ is precisely $k$, the contribution of $i$ to duskiness can change by $2k$ when you move $i$, in case the geodesic jumps on the other side. Let's call this a sign flip.

Suppose first that $c_i, c_{i+1} > 0$, i.e. both values want to move in the same direction along the cycle (counterclockwise the way I picture it). Applying the generator moves $i$ in the "correct" direction, and $i+1$ in the "wrong" direction. Now, the contribution to huskiness from $i$ is $-1$, and the contribution to oriented duskiness from $i$ is $-1/n$ as well. The contribution of $i+1$ to huskiness is either $0$ or $1$. If it is $1$, then there is no sign flip for $i+1$, so the contribution of $i+1$ to oriented duskiness is $+1/n$. If the contribution of $i+1$ to huskiness is $0$, then there was a sign flip, and thus its contribution to oriented duskiness is $-2k$. The maximal possible contribution of the swap to muskiness happens in the latter case, in the case when additionally the orientation of duskiness is such that muskiness decreases, and in this case the contribution to muskiness is $-1+0-1/n-2k/n = -2$. The case $c_i, c_{i+1} < 0$ is exactly analogous (though the orientation of duskiness is flipped).

Suppose then $c_i > 0, c_{i+1} < 0$, i.e. both of the two move in the direction they want to move. Then huskiness clearly decreases by two after the swap. Since both move in the direction they want to, there is no sign flip, and the changes in oriented duskiness cancel out. Thus, muskiness changes by $-2$ in this case.

Suppose then $c_i < 0, c_{i+1} > 0$, i.e. both of the two move in the "wrong direction". Then huskiness does not decrease, and may increase or stay invariant (for $i$ and $i+1$ separately). Oriented duskiness, thus also duskiness, may change by at most by $2 \cdot 2k / n < 2n$. Thus, muskiness can decrease by at most $2$ in this case.

There's also the cases $(c_i = 0, c_{i+1} > 0)$ and $(c_i = 0, c_{i+1} < 0)$ and $(c_i = 0, c_{i+1} = 0)$ (and a few more that are symmetric). These cases are easy and similar to the ones above (maybe I could've directly incorporated them somewhere). The huskiness increases in each case and the change in duskiness is not sufficent to counteract that.

(Square.)

$\endgroup$
8
  • $\begingroup$ The comment of Gerhard Paseman on the question seems to conjecture the optimality of the half-rotation. $\endgroup$
    – Ville Salo
    May 8, 2020 at 8:24
  • $\begingroup$ In mathoverflow.net/questions/31364 I ask about inversion density. It may be that a related metric to inversion density (somewhere between huskiness and friskiness) would add benefit to this exposition. Thanks for the mention. Gerhard "You Look Like A Skier" Paseman, 2020.05.08. $\endgroup$ May 8, 2020 at 16:41
  • $\begingroup$ Well first of all if you need help renaming "inversion density" to something more descriptive, I may have some ideas! Your question looks interesting, though I admit I don't directly see in what sense this notion is between $h$ and $f$. $\endgroup$
    – Ville Salo
    May 8, 2020 at 18:51
  • $\begingroup$ I understood you meant that something related to inversion density might be useful to add to my answer, but I realize you may also have meant that something like a huskiness/friskiness version of inversion density may be useful for your question. Maybe I is no good English. $\endgroup$
    – Ville Salo
    May 8, 2020 at 18:53
  • $\begingroup$ (Ok I'm pretty sure you meant the first one. Sorry, I'm pretty sleep-deprived from thinking up this answer last night and other reasons.) $\endgroup$
    – Ville Salo
    May 8, 2020 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.