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.