Minimal Antichains in Well-founded Quasi-orders with an Application to Tournaments

Authors: Cherlin G.L.¹; Latka B.J.²

Source: Journal of Combinatorial Theory, Series B, Volume 80, Number 2, November 2000 , pp. 258-276(19)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

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 _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 _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 [18]. Copyright 2000 Academic Press.

Language: English

Document Type: Research article

Affiliations: 1: Department of Mathematics, Hill Center, Rutgers University, Piscataway, New Jersey, 08855 2: Department of Mathematics, Lafayette College, Easton, Pennsylvania, 18042

Publication date: 2000-11-01