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