Minimal Antichains in Well-founded Quasi-orders with an Application to Tournaments
✍ Scribed by Gregory L. Cherlin; Brenda J. Latka
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 190 KB
- Volume
- 80
- Category
- Article
- ISSN
- 0095-8956
No coin nor oath required. For personal study only.
✦ Synopsis
We investigate the minimal antichains (in what is essentially Nash-Williams' sense) in a well-founded quasi-order. We prove the following finiteness theorem: If Q is a well-founded quasi-order and k a fixed natural number, then there is a finite set 4 k of minimal antichains of Q with the property that for any ideal I of Q obtained by excluding at most k elements of Q, I is well-quasi-ordered if and only if its intersection with each antichain in 4 k is finite. When applied in a suitably sharpened form to an algorithmic problem arising in model theory, this yields a strengthening of the main result of .