Combinatorics of Skew Tableaux and Flow Polytopes

枚举组合学是研究计数有限物体的数学领域，在数学和科学的许多领域都有强大的应用，包括表示理论、几何、概率论、统计力学和理论计算机科学。在计算机科学、代数和优化中，组合学中有两个重要的问题是，有多少种方法来订购具有特定约束的对象/任务，以及通过网络运输货物。本文利用半序集和多面体这两个令人着迷的数学对象来研究这两个问题的特殊情况。这个项目的主题是对学生开放的，项目包括与学生合作。此外，项目中研究的对象可以可视化，并将通过视频、学生讲座和STEM外展活动传播。部分有序集是组合学和计算机科学中的基本对象。有限偏序集的复杂度的一个度量是它的线性扩展的数目：它的元素的排序与偏序集的顺序相容的数目。本课题的第一部分研究了代数组合中出现的某些偏序族的线性扩展，这些偏序族可以像（偏）杨图和树（不一定有根）的偏集一样有效地计算。使用的工具包括来自几何的新的正公式，用于计算倾斜的杨表和用于计算树木线性扩展的行列式恒等式。项目的第二部分研究了图或网络的流动多面体以及这些多面体的体积、点阵数和三角剖分。这个项目有两个主要目标。第一个是使用新的对象来计算流多面体的Ehrhart系列，这些对象对这些多面体的体积进行编码。第二个目标是研究流动多面体与另一类多面体（广义复面体）共享的现象，即多面体的体积与相关多面体的晶格点数之间的关系。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Enumerative combinatorics is an area of mathematics that studies counting finite objects and has powerful applications in numerous areas of math and science including representation theory, geometry, probability, statistical mechanics, and theoretical computer science. Two important questions in combinatorics that are of interest in computer science, algebra and optimization are how many ways are there to order objects/tasks with certain constraints and to transport goods through a network. This research studies special cases of these two problems using two fascinating mathematical objects called partially ordered sets and polytopes. The topics of this project are accessible to students and the project includes collaboration with students. Also, the objects studied in the project can be visualized and will be disseminated through videos, student lectures, and STEM outreach activities. Partially ordered sets are fundamental objects in combinatorics and computer science. A measure of the complexity of a finite poset with is its number of linear extensions: the number of orderings of its elements compatible with the order of the poset. The first part of this project studies linear extensions for certain families of partial orders that appear in algebraic combinatorics and can be computed efficiently like posets of (skew) Young diagrams and trees (not necessarily rooted). The tools used include new positive formulas coming from geometry to count skew Young tableaux and determinantal identities for counting linear extensions of trees. The second part of the project studies flow polytopes of graphs or networks and the volumes, the number of lattice points and triangulations of these polytopes. This project has two main goals. The first one is to compute the Ehrhart series of flow polytopes using new objects that encode the volume of these polytopes. The second goal is to study a phenomenon that flow polytopes share with another family of polytopes called generalized permutahedra relating the volume of a polytope with the number of lattice points of a related polytope.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.