Motivation. I am working with a database software that allows you to sort the fields of any given table in the following peculiar way. Suppose your fields are numbered $1,\ldots, 18$. Next to every field there is an editable number indicating its position.
Assume you want to move field $4$ to position $11$. Then you click the editable position number next to field $4$ (which at the moment also says "$4$") and enter number $12$ (!). Then fields $1,2,3$ remain unchanged, the positions of the fields $5,\ldots, 11$ get decreased by $1$, the old $4$ does get position $11$, and finally fields $12,\ldots, 18$ remain the same. So let us call this kind of primitive operation a insert-and-shift-operation. At all times, all the fields are numbered $1,\ldots,18$. The operation of moving a field from a high position to a low position works in an analogous way. At all times, all the fields are numbered $1,\ldots,18$. I was wondering about how many insert-and-shift moves are needed at most to reach any given permutation.
Formal question. Let $n\geq 2$ be an integer, and let $[n] = \{1,\ldots,n\}$. For $s\in [n-1]$ and $t\geq s+2$ (so $t\in [n+1]$) we consider the insert-and-shift map $$\newcommand{\sst}{\sigma_{s,t}}\sst:[n]\to[n]$$ given by
- $\sst(k) = k$ for $k\in \{1,\ldots,s-1\}\cup \{t,\ldots,n\}$ (meaning everything stays the same outside the interval $[s,t-1]$),
- $\sst(s) = t-1$ ($s$ moves to position $t-1$), and
- $\sst(x) = x-1$ for $x\in \{s+1,\ldots,t-1\}$ (everything in the interval $[s+1,t-1]$ gets decreased).
Note that every $\sst$ is a permutation on $[n]$. Let $S_n$ be the collection of all permutations of $[n]$ and let $\pi\neq \psi \in S_n$ form an edge if there are $s\in [n-1]$ and $t\geq s+2$ such that $\pi = \sst \circ \psi$ or $\psi = \sst \circ \pi$. Let us call the resulting graph $\newcommand{\Gn}{\mathbf{G}_n}\Gn$.
Questions. In terms of $n$, what is the diameter of $\Gn$?
