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-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 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 with repeatable patterns, which we introduce. © The authors.
Original languageEnglish
JournalCombinatorial Theory
Volume4
Issue number2
DOIs
StatePublished - 27 Sep 2024

    Research areas

  • k-sets, permutations, Reduced words, weakly separated, wiring diagram

ID: 126221572