The structure of interval orders with no infinite antichain
Preprint
Abstract
We prove that every interval order $P$ with no infinite antichain has a Gallai decomposition. That is, $P$ is a lexicographical sum of proper interval orders over a chain, an antichain or a prime interval order. This is a consequence of the fact that the tree decomposition of a graph into robust modules, as introduced by Courcelle and Delhommé (Theoretical Computer Science \textbf{394} (2008) 1--38), is chain finite whenever the graph has no infinite independent sets. Next, we prove that every prime interval order with no infinite antichain is at most countable and scattered. Furthermore, for each countable ordinal $α$ we exhibit an example of a well-quasi-ordered prime interval order $P_α$ whose chain of maximal antichains has Hausdorff rank $α$.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Inductive Characterizations of Finite Interval Orders and SemiordersOrder, 2009
- Critically prime interval ordersDiscrete Mathematics, 2007
- An obvious proof of Fishburn's interval order theoremDiscrete Mathematics, 1993
- Theory of 2-structures, part II: Representation through labeled tree familiesTheoretical Computer Science, 1990
- A note on Dilworth's theorem in the infinite caseOrder, 1987
- Ordered sets with no chains of ideals of a given typeOrder, 1984
- On the Cofinality of Partially Ordered Sets1982
- Linear Extensions of Ordered Sets1982
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967
- Grundz ge einer Theorie der geordneten MengenMathematische Annalen, 1908