Counting self-dual interval orders

Abstract

In this paper, we first derive an explicit formula for the generating function that counts unlabeled interval orders (a.k.a. (2+2)-free posets) with respect to several natural statistics, including their size, magnitude, and the number of minimal and maximal elements. In the second part of the paper, we derive a generating function for the number of self-dual unlabeled interval orders, with respect to the same statistics. Our method is based on a bijective correspondence between interval orders and upper-triangular matrices in which each row and column has a positive entry.

Keywords

• interval orders
• (\textrm2+2)-free posets
• self-dual posets
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]