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.
@article{10_37236_8560,
author = {Cara Monical and Benjamin Pankow and Alexander Yong},
title = {Reduced word enumeration, complexity, and randomization},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {2},
doi = {10.37236/8560},
zbl = {1491.05190},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8560/}
}
TY - JOUR
AU - Cara Monical
AU - Benjamin Pankow
AU - Alexander Yong
TI - Reduced word enumeration, complexity, and randomization
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/8560/
DO - 10.37236/8560
ID - 10_37236_8560
ER -
%0 Journal Article
%A Cara Monical
%A Benjamin Pankow
%A Alexander Yong
%T Reduced word enumeration, complexity, and randomization
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8560/
%R 10.37236/8560
%F 10_37236_8560
Cara Monical; Benjamin Pankow; Alexander Yong. Reduced word enumeration, complexity, and randomization. The electronic journal of combinatorics, Tome 29 (2022) no. 2. doi: 10.37236/8560
