Representations and Linear Extensions of (Unit) Interval Orders

Sooa Song (Université du Québec à Montréal)

Unit interval orders (UIOs), which are more generally interval orders (IO), are certain partially ordered sets that are related to symmetric functions and knot theory. UIOs have two encodings as Dyck paths; one based on incomparable pairs and another via part listings. These encodings are related by Haglund’s zeta map, as shown by Gélinas-Segovia-Thomas. On the other hand, interval orders have two well-known encodings: ascent sequences and Fishburn matrices. We present three results: (1) an enumeration of height- and width-restricted UIOs, revealing connections to the zeta map, (2) an algorithm for counting linear extensions of UIOs using these encodings, and (3) a related algorithm to compute linear extensions of interval orders through Fishburn matrices.

 Overview  Program