Decomposing Labeled Interval Orders as Pairs of Permutations

  • Anders Claesson
  • Stuart A. Hannah
Keywords: ballot matrix, composition matrix, sign reversing involution, interval order, 2 2-free poset, Fishburn, ascent bottom


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.
Article Number