Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD. / Gaetz, C.; Gao, Y.; Jiradilok, P.; Nenashev, G.; Postnikov, A.
в: Combinatorial Theory, Том 4, № 2, 27.09.2024.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD
AU - Gaetz, C.
AU - Gao, Y.
AU - Jiradilok, P.
AU - Nenashev, G.
AU - Postnikov, A.
N1 - Export Date: 21 October 2024 Сведения о финансировании: National Science Foundation, NSF, DMS-2103121 Сведения о финансировании: ONR-N00014-20-1-2826 Сведения о финансировании: 622132 Сведения о финансировании: Knut och Alice Wallenbergs Stiftelse, KAW 2017.0394 Текст о финансировании 1: C.G. was partially supported by an NSF Fellowship under grant DMS-2103121. P.J. was supported by Elchanan Mossel\u2019s Vannevar Bush Faculty Fellowship ONR-N00014-20-1-2826 and by Elchanan Mossel\u2019s Simons Investigator award (622132). G.N. was supported by the Knut and Alice Wallenberg Foundation, KAW 2017.0394.
PY - 2024/9/27
Y1 - 2024/9/27
N2 - 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.
AB - 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.
KW - k-sets
KW - permutations
KW - Reduced words
KW - weakly separated
KW - wiring diagram
UR - https://www.mendeley.com/catalogue/0dfa5994-0847-3f7e-bd92-33b770984c11/
U2 - 10.5070/c64264252
DO - 10.5070/c64264252
M3 - статья
VL - 4
JO - Combinatorial Theory
JF - Combinatorial Theory
SN - 2766-1334
IS - 2
ER -
ID: 126221572