3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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$
    – Sam Hopkins
    Commented 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
    Commented 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$
    – Sam Hopkins
    Commented 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
    Commented Dec 24, 2021 at 5:11

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ (Posting this live from a talk of Alex Postnikov mentioning this.) $\endgroup$
    – Christian Stump
    Commented Jan 10, 2022 at 12:32
1
$\begingroup$

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

Improve this answer
$\endgroup$
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
    Commented Dec 24, 2021 at 4:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .