EUVIMEDEUVIMED entdecken
Crossref

Reduced Word Enumeration, Complexity, and Randomization

Cara Monical, Benjamin Pankow, Alexander Yong

The Electronic Journal of Combinatorics · 03.06.2022 · 29 (2)

DOI: 10.37236/8560 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 03.06.2022. Verfasst von Cara Monical und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A reduced word of a permutation w is a minimal length expression of w as a product of simple transpositions. We examine the computational complexity, formulas and (randomized) algorithms for their enumeration. In particular, we prove that the Edelman-Greene statistic, defined by S. Billey-B. Pawlowski, is typically exponentially large. This implies a result of B. Pawlowski, that it has exponentially growing expectation. Our result is established by a formal run-time analysis of A. Lascoux and M. P. Schützenberger's transition algorithm. The more general problem of Hecke word enumeration, and its closely related question of counting set-valued standard Young tableaux, is also investigated. The latter enumeration problem is further motivated by work on Brill-Noether varieties due to M. Chan-N. Pflueger and D. Anderson-L. Chen-N. Tarasca.

Zitieren

APA

Monical, C., Pankow, B., & Yong, A. (2022). Reduced Word Enumeration, Complexity, and Randomization. The Electronic Journal of Combinatorics, 29(2). https://doi.org/10.37236/8560

Vancouver

Monical C, Pankow B, Yong A. Reduced Word Enumeration, Complexity, and Randomization. The Electronic Journal of Combinatorics. 2022;29(2). doi:10.37236/8560

BibTeX
@article{Monical2022,
  author = {Monical, Cara and Pankow, Benjamin and Yong, Alexander},
  title = {Reduced Word Enumeration, Complexity, and Randomization},
  journal = {The Electronic Journal of Combinatorics},
  year = {2022},
  volume = {29},
  number = {2},
  doi = {10.37236/8560}
}
Kostenlos starten →