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.

  • $\begingroup$ $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$. $\endgroup$ Dec 20, 2021 at 22:05
  • $\begingroup$ @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? $\endgroup$
    – David Pal
    Dec 20, 2021 at 23:11
  • $\begingroup$ 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. $\endgroup$ Dec 20, 2021 at 23:17
  • $\begingroup$ 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. $\endgroup$
    – David Pal
    Dec 24, 2021 at 5:11

2 Answers 2


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

  • 1
    $\begingroup$ (Posting this live from a talk of Alex Postnikov mentioning this.) $\endgroup$ 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$.

  • $\begingroup$ 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. $\endgroup$
    – David Pal
    Dec 24, 2021 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.