Thesis
Interval order enumeration
Downloadable Content
Download PDF- Creator
- Rights statement
- Awarding institution
- University of Strathclyde
- Date of award
- 2015
- Thesis identifier
- T14188
- Person Identifier (Local)
- 201177417
- Qualification Level
- Qualification Name
- Department, School or Faculty
- Abstract
- This thesis continues the study of interval orders and related structures, containing results on both the labeled and unlabeled variants. Following a result of Eriksen and Sjöstrand (2014) we identify a link between structures following the Fishburn distribution and Mahonian structures. This is used to detail a technique for the construction of Fishburn structures (structures in bijection with unlabeled interval orders) from appropriate Mahonian structures. This technique is introduced on a bivincular pattern of Bousquet-Mélou et al. (2010) and then used to introduce a previously unconsidered class of matchings; explicitly, zero alignment matchings according to the number of arcs which are both right-crossed and left-nesting. The technique is then used to identify a statistic on the factorial posets of Claesson and Linusson (2011) following the Fishburn distribution. Factorial posets mapped to zero by this statistic are canonically labeled factorial posets which may alternatively be viewed as unlabeled interval orders. As a consequence of our approach we find an identity for the Fishburn numbers in terms of the Mahonian numbers and discuss linear combinations of Fishburn patterns in a manner similar to that of the Mahonian combinations of Babson and Steingrímsson (2001). To study labeled interval orders 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. Adapting a bijection of Dukes, Jelínek and Kibitzke (2011), 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.
- Resource Type
- DOI
- Date Created
- 2015
- Former identifier
- 1247245
Relations
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
PDF of thesis T14188 | 2021-07-02 | Public | Download |