Reduced Word Enumeration, Complexity, and Randomization
Reduced Word Enumeration, Complexity, and Randomization
复制标题
减少单词枚举、复杂性和随机化
DOI：
--
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
A. Yong
中科院分区：
文献类型：
--
作者：
C. Monical;Benjamin Pankow;A. Yong
置换w的约化字是w作为简单置换的乘积的最小长度表达式。我们研究计算的复杂性，公式和（随机）算法，其枚举。特别地，我们证明了S.比利湾Pawlowski，通常是指数级的。这意味着B的结果。Pawlowski，它有指数增长的期望。我们的结果是通过对A. Lascoux和M. P. Schützenberger的转换算法。更一般的问题Hecke字计数，其密切相关的问题，计数集值标准杨tableaux，也进行了研究。后一个计数问题是由M.陈Pflueger和D.安德森湖陈N塔拉斯卡
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.
Brill-Noether 品种的欧拉特征
影响因子：
1.3
作者：
Chan, Melody;Pflueger, Nathan
通讯作者：
Pflueger, Nathan
Brill–Noether 轨迹的 ? 类和行列式
影响因子：
1
作者：
Anderson, Dave;Chen, Linda;Tarasca, Nicola
通讯作者：
Tarasca, Nicola