Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06693 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916476857876480 |
|---|---|
| author | Pouzet, Maurice Zaguia, Imed |
| author_facet | Pouzet, Maurice Zaguia, Imed |
| contents | 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 $α$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06693 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The structure of interval orders with no infinite antichain Pouzet, Maurice Zaguia, Imed Combinatorics 06A6, 06F15 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 $α$. |
| title | The structure of interval orders with no infinite antichain |
| topic | Combinatorics 06A6, 06F15 |
| url | https://arxiv.org/abs/2411.06693 |