The structure of interval orders with no infinite antichain

Abstract

We prove that if $G=(V,E)$ is a nonprime graph with either no infinite independent set or no infinite clique, then every vertex of $G$ belongs to a maximal strong module distinct from $V$. In particular, $G$ admits a Gallai decomposition. As a consequence, we obtain that every interval order $P$ with no infinite antichain admits a Gallai decomposition. That is, $P$ is a lexicographical sum of interval orders distinct from $P$ indexed by either a chain, an antichain, or a prime interval order. Next, we prove that every prime interval order with no infinite antichain is at most countable and does not embed a copy of the chain of rational numbers. Finally, for each countable ordinal $\alpha$, we construct a well-quasi-ordered prime interval order $P_{\alpha }$ whose chain of maximal antichains has Hausdorff rank $\alpha$.

26 pages, 2 figures