Decomposing Labeled Interval Orders as Pairs of Permutations

Anders Claesson, Stuart A. Hannah


We introduce ballot matrices, a signed combinatorial structure whose definition naturally follows from the generating function for labeled interval orders. A sign reversing involution on ballot matrices is defined. We show that matrices fixed under this involution are in bijection with labeled interval orders and that they decompose to a pair consisting of a permutation and an inversion table. To fully classify such pairs, results pertaining to the enumeration of permutations having a given set of ascent bottoms are given. This allows for a new formula for the number of labeled interval orders.


ballot matrix; composition matrix; sign reversing involution; interval order; 2+2-free poset; Fishburn; ascent bottom

Full Text: