Combinatorics of Skew Tableaux and Flow Polytopes

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

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.