1

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$?

Dominic van der Zypen
  • 45,374
  • 1
    Such operation may be viewed as a singleton transposition. This paper is relevant: https://www.sciencedirect.com/science/article/abs/pii/S0304397522001542 – Max Alekseyev Mar 23 '24 at 01:21
  • 1
    @MaxAlekseyev may be viewed in which sense? The graphs are different: the Dominic's graph is not bipartite – Fedor Petrov Mar 23 '24 at 21:21
  • @FedorPetrov: In the sense of transpositions as they are defined in bioinformatics (see linked paper for some background). I'm not sure what bipartite graph you refer to. – Max Alekseyev Mar 23 '24 at 22:14
  • 1
    @MaxAlekseyev Usual Cayley graph of $S_n$ with transpositions as generators – Fedor Petrov Mar 24 '24 at 04:08
  • @FedorPetrov: We seem to talk about different kind of transpositions. Under singleton transposition I mean cutting off an element of permutation and inserting it at some other position, not necessarily exchanging two consecutive elements. – Max Alekseyev Mar 24 '24 at 04:15
  • @MaxAlekseyev I was thinking transpositions are exchanging two (not necessarily consecutive) elements: https://en.m.wikipedia.org/wiki/Cyclic_permutation – Fedor Petrov Mar 24 '24 at 04:23
  • @FedorPetrov: "Consecutive" was my mistyping, but the point is that transposition in math is not the same thing as transposition in bioinformatics, while singleton transposition is a partial case of the latter. – Max Alekseyev Mar 24 '24 at 04:34
  • @FedorPetrov: In short, while transposition in math exchanges any two elements (singletons), transposition in computational biology / bioinformatics exchanges two consecutive blocks, each of which may be composed of one or more elements. It may be also viewed as "transposing" (cutting off and inserting in a new place) of a single block called transposon, hence the name. If transposon is a singleton, we get the operation considered by OP. – Max Alekseyev Mar 24 '24 at 18:12
  • 2
    @MaxAlekseyev cool. By the way - that "Masterball/Globe" puzzle is made of generators which swap/transpose consecutive blocks - see pictures here https://math.stackexchange.com/q/4848434/21498, plus cyclic (again consecutive). Diameters seems linear: https://www.kaggle.com/code/snopoff/structural-analysis-of-globe-groups?scriptVersionId=167276284&cellId=31 May be it can be proved and answer: https://mathoverflow.net/q/462618/10446 – Alexander Chervov Mar 24 '24 at 18:56
  • 2
    @AlexanderChervov: At first glance, generators there are restricted to certain size of blocks. In bioinformatics and comparative genomics, there is generally no such restriction, and even then the problems in analysis of transpositions are among the hardest ones, with some known to be NP-compete - e.g., see https://arxiv.org/abs/1011.1157 – Max Alekseyev Mar 25 '24 at 13:05
  • 1
    @MaxAlekseyev Yes, you are right. Nevertheless according to your experience - what do you think - can be simple to esimate diameter of the "Globe=Masterball" at least in some cases ? Another question: the trick used Helfgot in his breakthrough papers on diameter estimation for many groups - first find way to represent 3-cycles (small support permutations) , and then 3-cycles - generate everything in more easy way. Actually the similar trick is used by profi Rubik cube solvers - it is called "pif-paf" or "commutator" moves. In bioinformatics - have you seen such kind of ideas ? – Alexander Chervov Mar 28 '24 at 11:53

1 Answers1

5

Diameter equals $n-1$.

For an upper bound, we should get from every permutation an identical one by at most $n-1$ such transformations. Just place 1 to its place (one transformation is always enough), then 2, etc.

For a lower bound, note that after each transformation the relative order of all elements but one is preserved. Thus, after $k$ transformation the relative order of $n-k$ elements is preserved. If $k\leqslant n-2$, this yields that we can not reverse the order by $k$ operations.

Fedor Petrov
  • 102,548