Swaps in a permutation across an index

Question

We are given two positive integers $N$ and $K$ such that $K < N$. We start with an array $A=[1,2,\dots,N]$. We can choose an arbitrary index $i \in \{1,2,\dots,N-1\}$ and we can swap $A[i]$ with $A[i+1]$ provided that $A[i] < A[i+1]$. We do such swaps until no more such swaps are possible. (This happens when the array $A$ is completely reversed, i.e., $A=[N, N-1, \dots, 1]$ after exactly $N(N-1)/2$ swaps, since every swap increases the number of inversions by $1$.) Let $S_{N,K}$ be the maximum possible number of swaps of $A[K]$ and $A[K+1]$ that can happen (taken over all possible legal sequences of swaps).

What are the best known lower and upper bounds for $S^*_N = \max\{S_{N,1}, S_{N,2}, \dots, S_{N,N-1}\}$ in terms of $N$?

Note: The trivial bounds $N-1 = S_{N,1} \le S^*_N \le N(N-1)/2$ are too loose for my taste. I would like to have lower and upper bounds that are within a constant factor of each other.

Answer 1

It seems that the paper The Maximum Multiplicity of a Generator in a Reduced Word by Christian Gaetz, Yibo Gao, Pakawut Jiradilok, Gleb Nenashev and Alexander Postnikov is the state of the art concerning this problem:

They write $\mathcal{M}(k,n)$ for your $S(n,k)$ and show that for fixed $k$ and $n \rightarrow \infty$ one has $\mathcal{M}(k,n) = c_k n + p_k(n)$ for a constant $c_k$ and a periodic function $p_k$. In particular, it grows linearly in $n$ for $k$ fixed.

They do not seem to give an anwer for the maximum over all $k$ though.

(Disclaimer: I have not read the paper, but only reproduce their abstract here.)

Answer 2

An easy upper bound for $S^*_N$ is $\lceil N(N-1)/4 \rceil$, the integer ceiling of half the length of a legal sequence taking $[1,\ldots,N]$ to $[N,\ldots, 1]$. If some transposition $(i, i+1)$ occurred more often in the sequence, there would be two $(i, i+1)$ in a row which would cancel each other out / cannot happen in a legal sequence.

A small example shows that this bound is sharp. In the Dauvergne paper Sam mentioned in the comments, Figure 5 on p8 shows the permutahedron, a visualization of the $N = 4$ case. By Stanley's formula (1) on p3, there are 16 legal paths from $[1,2,3,4]$ at the bottom to $[4,3,2,1]$ on the top, each of length 6. Some of these paths have two transpositions each of $(1,2)$, $(2,3)$, and $(3,4)$, while some have an unequal distribution. The one along the right-hand side of the figure, for example, is red-green-red-blue-green-red, i.e., $(3,4),(2,3),(3,4),(1,2),(2,3),(3,4)$. By the reasoning above, no legal path / reduced word could have a certain transposition in 4 of the 6 steps, so $S^*_4 = 3$. The fussiness about the integer ceiling comes from the easier example of $N=3$ where the only possibilities are $(1,2),(2,3),(1,2)$ and $(2,3),(1,2),(2,3)$ which shows $S^*_3 = 2 = \lceil 3/2 \rceil$.

---

Edit: After convincing myself that there are no examples of legal length 10 sequences for $N = 5$ with any one transposition occurring 5 times, I wonder if there's actually an upper bound for $S^*_n$ that's linear in $N$. The intuition is that there are "balanced" sequences where each of the $N-1$ transpositions appear roughly an equal number of times (frequencies differ by at most 1); how much could the frequency for a given transposition vary from that?

Data: The balanced sequence $$(1,2),(4,5),(2,3),(3,4),(1,2),(4,5),(2,3),(3,4),(1,2),(2,3)$$ has frequencies $3,3,2,2$, while the sequence $$(1,2),(2,3),(3,4),(4,5),(1,2),(2,3),(3,4),(1,2),(2,3),(1,2)$$ has frequencies $4,3,2,1$.