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