Reduced word enumeration, complexity, and randomization

Cara Monical, Benjamin Pankow, Alexander Yong

Research output: Contribution to journalArticlepeer-review


A reduced word of a permutation w is a minimal length expression of w as a product of simple transpositions. We examine 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 complexity analysis of A. Lascoux-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. We also state some related problems about counting compu-tational complexity.

Original languageEnglish (US)
Article number#P2.46
JournalElectronic Journal of Combinatorics
Issue number2
StatePublished - 2022

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Reduced word enumeration, complexity, and randomization'. Together they form a unique fingerprint.

Cite this