Reduced Word Enumeration, Complexity, and Randomization

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. Pawlows...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2022-06, Vol.29 (2)
Main Authors: Monical, Cara, Pankow, Benjamin, Yong, Alexander
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1077-8926
1077-8926
DOI:10.37236/8560