paper

Repeatable patterns and the maximum multiplicity of a generator in a reduced word

arXiv:2204.03033 · doi:10.5070/C64264252

Abstract

We study the maximum multiplicity $M (k, n)$ of a simple transposition $s_{k} = (k k + 1)$ in a reduced word for the longest permutation $w_{0} = n n - 1 \dots 21$ , a problem closely related to much previous work on sorting networks and on the " $k$ -set" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed $k$ and sufficiently large $n$ , the optimal density is realized by paths which are periodic in a precise sense, so that \[ \mathcal{M}(k,n)=c_k n + p_k(n) \] for a periodic function $p_{k}$ and constant $c_{k}$ . In fact we show that $c_{k}$ is always rational, and compute several bounds and exact values for this quantity with "repeatable patterns", which we introduce.

30 pages; to appear in Combinatorial Theory