Repeatable patterns and the maximum multiplicity of a generator in a reduced word
Abstract
We study the maximum multiplicity \(\mathcal{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 \: \cdots \: 2 \: 1\), 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.
Mathematics Subject Classifications: 05A05, 05A16, 05E99
Keywords: Reduced words, permutations, \(k\)-sets, wiring diagram, weakly separated