A Decision Problem Involving Tournaments
Gregory L. Cherlin, Brenda J. Latka · 1996
A class of finite tournaments determined by a set of "forbidden subtournaments" is wellquasi -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, 3 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 3 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. Keywords: antichain, decidability, forb...