Latka Abstract

Next: lesniak Abstract Up: Index of Abstracts Previous: Sundaram Abstract


Forbidden Subtournaments and Antichains
Brenda J. Latka
Lafayette College and DIMACS
latka@dimacs.rutgers.edu




Classes of tournaments can be defined by sets of forbidden subtournaments. Is there an infinite antichain (a set of incomparable elements) in such a class? For finite tournaments, this is equivalent to asking if the class is well-quasi-ordered. In general, it is not known if an algorithm exists to decide whether or not a class of finite tournaments determined by $k$ forbidden subtournaments has an infinite antichain. We show, however, that given any integer $k$, there is a finite set of infinite antichains, $\Lambda_k$, with the following property: if any class defined by $k$ forbidden subtournaments contains an infinite antichain, then a subset of an element of $\Lambda_k$ must be such an antichain. By refining this analysis and using an earlier result giving an explicit algorithm for the case $k=1$, we show that there exists an algorithm which decides whether or not a class of finite tournaments determined by two forbidden subtournaments is well-quasi-ordered.