5
$\begingroup$

For two permutations $\pi,\tau \in S_n$, we say they are related by a prefix reversal if there exists $t$ such that $\tau(i) = \pi(i)$ for $i\ge t$ and $\tau(i) = \pi(t-i)$ for $i<t$. Similarly, we say they are related by a suffix reversal if there exists $t$ such that $\tau(i) =\pi(i)$ for $i< t$ and $\tau(i) = \pi(n-i+t)$ when $i\ge t$. We define $G_n$ to be the graph with vertex set $S_n$ with $\pi,\tau$ being adjacent if they are related by a prefix or suffix reversal.

Let $h(n)$ be the diameter of $G_n$. Has the growth of this quantity been directly studied?

If I'm not mistaken, the argument proving the best known lower bound to the pancake problem should also work here, establishing $h(n)\ge 15n/14-O(1)$. Meanwhile, I have found a proof that $h(n)\le 3n/2+O(1)$. I am most interested in determining if this upper bound is already known.

$\endgroup$
2

0

Your Answer

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