Combinatorics of Skew Tableaux and Flow Polytopes

University Of Massachusetts Amherst, Amherst MA

Investigators

Abstract

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.