## DIMACS TR: 96-11

## A Decision Problem Involving Tournaments

### Authors: Gregory L. Cherlin, Brenda J. Latka

**
Abstract:
**

A class of finite tournaments determined by a set of ``forbidden
subtournaments'' is well-quasi-ordered if and only if it contains no
infinite antichain (a set of incomparable elements). It is not known
if there is an algorithm which decides whether or not a class of
finite tournaments determined by a finite set of forbidden
subtournaments has this property. We prove a noneffective finiteness
theorem bearing on the problem. We show that for each fixed $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 cofinite 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.
footnote:

This work was the result of the authors' collaboration during the 95/96
Special Year on Logic and Algorithms.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-11.ps.gz

DIMACS Home Page