Standard

REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD. / Gaetz, C.; Gao, Y.; Jiradilok, P.; Nenashev, G.; Postnikov, A.

In: Combinatorial Theory, Vol. 4, No. 2, 27.09.2024.

Research output: Contribution to journal › Article › peer-review

Harvard

Gaetz, C, Gao, Y, Jiradilok, P, Nenashev, G & Postnikov, A 2024, 'REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD', Combinatorial Theory, vol. 4, no. 2. https://doi.org/10.5070/c64264252

APA

Gaetz, C., Gao, Y., Jiradilok, P., Nenashev, G., & Postnikov, A. (2024). REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD. Combinatorial Theory, 4(2). https://doi.org/10.5070/c64264252

Vancouver

Gaetz C, Gao Y, Jiradilok P, Nenashev G, Postnikov A. REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD. Combinatorial Theory. 2024 Sep 27;4(2). https://doi.org/10.5070/c64264252

Author

Gaetz, C. ; Gao, Y. ; Jiradilok, P. ; Nenashev, G. ; Postnikov, A. / REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD. In: Combinatorial Theory. 2024 ; Vol. 4, No. 2.

BibTeX

@article{8900f5f9e1944242a18e3a6c341c8832,
title = "REPEATABLE PATTERNS AND THE MAXIMUM MULTIPLICITY OF A GENERATOR IN A REDUCED WORD",
abstract = "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. {\textcopyright} The authors.",
keywords = "k-sets, permutations, Reduced words, weakly separated, wiring diagram",
author = "C. Gaetz and Y. Gao and P. Jiradilok and G. Nenashev and A. Postnikov",
note = "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.",
year = "2024",
month = sep,
day = "27",
doi = "10.5070/c64264252",
language = "Английский",
volume = "4",
journal = "Combinatorial Theory",
issn = "2766-1334",
publisher = "University of California Press",
number = "2",

}

RIS

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