Séminaire Lotharingien de Combinatoire, 85B.82 (2021), 12 pp.
Christian Gaetz, Yibo Gao, Pakawut Jiradilok, Gleb Nenashev and Alexander Postnikov
The Maximum Multiplicity of a Generator in a Reduced Word
We study the maximum multiplicity M(k,n) of a simple transposition sk = (k k+1) in a reduced word for the longest permutation w0 = n n-1 ... 2 1, a problem closely related to much previous work on sorting networks and on the "k-sets" problem. After reinterpreting the problem in terms of monotone weakly separated paths, we show that, for fixed k and growing n, the optimal collections are periodic in a precise sense, so that
M(k,n) = ckn + pk(n)
for a periodic function pk and constant ck. In fact we show that ck is always rational, and compute several bounds and exact values for this quantity.
Received: December 1, 2020.
Accepted: March 1, 2021.
Final version: April 29, 2021.
The following versions are available: