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

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₀ = 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) = c_kn + 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.

Received: December 1, 2020. Accepted: March 1, 2021. Final version: April 29, 2021.

The following versions are available:

PDF ( K)
TeX version