The proposal concerns several problems related to permutations, polytopes, and partially ordered sets (posets). There are a number of classes of convex polytopes whose combinatorial properties, especially their volumes and Ehrhart polynomials, will be investigated. The first of these polytopes generalizes a well-understood polytope whose volume (suitable normalized) is the number of alternating permutations of 1,2,...,n. The second class of polytopes consists of "half-open" variants of a hypersimplex and some generalizations thereof. There is a surprising connection with the enumeration of permutations according to their number of descents and number of excedances. The final class consists of the poorly understood valuation polytopes of posets. The PI will consider some posets related to group actions on other posets, the primary example being the action of the symmetric group on the lattice of partitions of a set. The resulting poset, a kind of quotient of the partition lattice, is a supersolvable and EL-shellable lattice, and it promises to have a host of interesting additional properties. Recent work on interval orders suggests extending these results to marked interval orders, a concept previously introduced by the PI. He hopes to find "marked analogues" of such recently studied concepts as ascent sequences, permutations avoiding a certain barred pattern, and Stoimenow involutions (or regular linearized chord diagrams). A related problem is to find a theory unifying the connection between certain classes of labelled and unlabelled objects. In 2007 K. Saito proved an intriguing result about trees that generalizes a theorem of Niven and de Bruijn (independently) about permutations. Saito conjectured that his result could be extended to all bipartite graphs. The PI will try to prove Saito's conjecture, first using techniques from the theory of the cd-index of an Eulerian poset. The PI will continue research with R. Du on the distribution of elements in the cycles of a product of two cycles, inspired originally by a conjecture of M. Bona. In particular, he will consider several open problems arising from his previous work with Du.
Polytopes, permutations, and posets are pervasive throughout mathematics. There are many deep and elegant theorems concerning them, but examples of these objects are limited for which there exist explicit descriptions of their fundamental invariants. New examples would open doors to applications, shed new light on the mathematics involved in the description of the invariants, and provide new connections between previously unrelated objects. Interval orders have numerous applications to such areas as sociology and psychology. An expansion of the theory of marked interval orders may have similar applications. Saito's conjecture hints at a generalization, that could have broad appicability, of a well-studied geometric concept.
