Reduced word enumeration, complexity, and randomization
Exact enumeration problems, generating functions (05A15) Symmetric functions and generalizations (05E05) Combinatorial aspects of representation theory (05E10) Combinatorial aspects of algebraic geometry (05E14) Grassmannians, Schubert varieties, flag manifolds (14M15) Analysis of algorithms and problem complexity (68Q25)
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 \textit{S. Billey} and \textit{B. Pawlowski} [J. Comb. Theory, Ser. A 127, 85--120 (2014; Zbl 1300.05313)], is typically exponentially large. This implies a result of \textit{B. Pawlowski} [Permutation diagrams in symmetric function theory and Schubert calculus. Seattle, WA: University of Washington (PhD Thesis) (2014), \url{https://digital.lib.washington.edu/researchworks/bitstream/handle/1773/26117/Pawlowski_washington_0250E_13742.pdf?sequence=1}], that it has exponentially growing expectation. Our result is established by a formal run-time analysis of Lascoux and Schützenberger's transition algorithm [\textit{A. Lascoux} and \textit{M.-P. Schützenberger}, Lett. Math. Phys. 10, 111--124 (1985; Zbl 0586.20007)]. 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 \textit{M. Chan} and \textit{N. Pflueger} [Trans. Am. Math. Soc. 374, No. 3, 1513--1533 (2021; Zbl 1464.14032)] and \textit{D. Anderson} et al. [``K-classes of Brill-Noether loci and a determinantal formula, Int. Math. Res. Not. 2022, No. 16, 12653--12698 (2022; \url{doi:10.1093/imrn/rnab025})]. We also state some related problems about counting computational complexity.
- On the expected number of commutations in reduced words
- scientific article; zbMATH DE number 3892611
- Some bounds on the complexity of words
- Reduction and irreducibility for words and tree-words
- Efficient lower bounds on the number of repetition-free words
- scientific article; zbMATH DE number 1738654
- Sorting and generating reduced words
- Algorithmic combinatorics on partial words
- A Littlewood-Richardson rule for the \(K\)-theory of Grassmannians.
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- An efficient algorithm for deciding vanishing of Schubert polynomial coefficients
- Approximating the permanent: A simple approach
- Balanced tableaux
- Combinatorial aspects of the \(K\)-theory of Grassmannians
- Euler characteristics of Brill-Noether varieties
- Factorization of the Robinson-Schensted-Knuth correspondence
- Flags, Schubert polynomials, degeneracy loci, and determinantal formulas
- Gröbner geometry of vertex decompositions and of flagged tableaux
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 2135025 (Why is no real title available?)
- Mathematics and computer science: coping with finiteness
- Noncommutative Schur functions and their applications
- On the asymptotic statistics of the number of occurrences of multiple permutation patterns
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
- On the number of reduced decompositions of elements of Coxeter groups
- Permutation patterns, Stanley symmetric functions, and generalized Specht modules
- Poset edge densities, nearly reduced words, and barely set-valued tableaux
- Quantum cohomology of partial flag manifolds
- Schubert polynomials and the Littlewood-Richardson rule
- Some combinatorial properties of Schubert polynomials
- Stable Grothendieck polynomials and \(K\)-theoretic factor sequences
- Symmetric functions, Schubert polynomials and degeneracy loci. Transl. from the French by John R. Swallow
- The complexity of computing the permanent
- The Hook Graphs of the Symmetric Group
- The sample size required in importance sampling
- Transition equations for isotropic flag manifolds.
- Enumerations relating braid and commutation classes
- Reduced word manipulation: patterns and enumeration
- Approximate counting of standard set-valued tableaux
- An inversion statistic for reduced words
- The maximum multiplicity of a generator in a reduced word
- Sorting and generating reduced words
- Reductions on Double Occurrence Words
- Bijecting hidden symmetries for skew staircase shapes
- On the \(q\)-enumeration of barely set-valued tableaux and plane partitions
- From quasi-symmetric to Schur expansions with applications to symmetric chain decompositions and plethysm
- Poset edge densities, nearly reduced words, and barely set-valued tableaux
This page was built for publication: Reduced word enumeration, complexity, and randomization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2144333)
