我院图论与组合团队在组合算法研究方面取得新进展
近日，我院图论与组合团队在国际权威数学期刊《Journal of Combinatorial Theory, Series A》上发表了题为“Eulerian-type polynomials over Stirling permutations and box sorting algorithm”的研究论文。我院马世美教授为论文的第一作者兼通讯作者。
欧拉多项式的研究起源于1736年欧拉关于幂级数求和问题的研究。在过去的一个多世纪里，欧拉多项式不断出现在代数组合、概率分布、几何拓扑、数值分析以及样条逼近问题的研究中。斯特林排列是1978年由布兰迪斯大学的Ira Gessel教授和美国科学院院士、麻省理工学院的Richard P. Stanley教授引入的。马世美教授和合作团队致力于研究排列统计理论和相关的多项式。围绕斯特林排列上的欧拉型多项式开展研究，2019年至今已有四篇成体系的论文发表在《Journal of Combinatorial Theory, Series A》上。这四篇论文合计121页，主要将经典组合方法和陈氏文法结合，引进了文法变换法、斯特林编码以及盒子排序算法等工具，给出了局部伽玛正性和双伽玛正性的定义，发现了一系列新的欧拉型组合统计量，率先把文法理论用于杨表理论和矩阵理论的研究，从多个角度揭示了斯特林排列和Coxeter群中的排列紧密相连。
最新发表的这篇论文首先简化了Ira Gessel教授的一个卷积公式。然后通过在斯特林排列上引入三个新的统计量，发现了一类限位斯特林排列上的六元统计量和B型Coxeter群上一组经典的六元统计量是同分布的。最后利用盒子排序算法非常简洁地建立了高阶微分算子展开式和标准杨表的联系，并发现了二阶欧拉多项式的三种新的组合展开式。盒子排序算法是一种研究高阶微分算子的具有普适性的组合算法。
《Journal of Combinatorial Theory, Series A》是组合数学界公认的权威期刊，以选稿严格著称，曾发表许多奠基性成果，平均每年仅刊发约70-80篇研究论文。该刊现为中科院期刊分区3区，中国数学会T2期刊，也是JCR分区1区。
