# Swaps in a permutation across an index

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.

• $S_{N,K}$ should be the maximum number of copies of the simple transposition $s_k=(k,k+1)$ in a reduced expression for the longest word $w_0 = n, n-1,\ldots, 1$. Dec 20, 2021 at 22:05
• @SamHopkins I don't understand the meaning of what you are saying. I guess I don't know the appropriate definitions. What is a "simple transposition"? What is a "reduced expression"? Can you please provide references to books or papers? Dec 20, 2021 at 23:11
• See for example the introduction of arxiv.org/abs/1802.08934 for an explanation of the connection between sorting networks and reduced decompositions. But really it's just a rephrasing of your question, not an answer. Dec 20, 2021 at 23:17
• I think it's a good idea to explain how did I come up with the problem. Trying to solve some linear programs, I ended up studying the following function: $\operatorname{top}_K:\mathbb{R}^N \to \mathbb{R}$, where $\operatorname{top}_K(x_1, x_2, \dots,x_N)$ is defined as the sum of $K$ largest numbers from $x_1, x_2, \dots, x_N$. The function is continuous, convex and piecewise linear. Consider the function along some line $g(t) = \operatorname{top}_K(x_1^{(0)} + t v_1, x_2^{(0)} + t v_2, \dots, x_N^{(0)} + t v_N)$. The function $g(t)$ has at most $S_{N,K}$ breakpoints. Dec 24, 2021 at 5:11

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

• (Posting this live from a talk of Alex Postnikov mentioning this.) Jan 10, 2022 at 12:32

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

• My colleague from work claims to have a lower bound $S_N^* \ge \Omega(N \log N)$. I will over the details of his proof and post it here. Dec 24, 2021 at 4:58