# Variant of the pancake problem

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. 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.

• Related on OEIS. Jan 7, 2022 at 19:11
• Did you yourself answer this? arxiv.org/abs/2211.14678 If so, you should add an answer here! And maybe update the MO "success stories" thread on meta Jan 23 at 14:55