Reduced word enumeration, complexity, and randomization

Abstract

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

23 pages. v2: added reference to University of Washington PhD thesis of B. Pawlowski, which proves a stronger version of Theorem 1.1

References in corpus (5)

• Schur P-positivity and involution Stanley symmetric functions
• The copies of any permutation pattern are asymptotically normal
• K-classes of Brill-Noether loci and a determinantal formula
• A formula for K-theory truncation Schubert calculus
• Word posets, complexity, and Coxeter groups

Cited by in corpus (1)

• On the $q$-Enumeration of Barely Set-Valued Tableaux and Plane Partitions