DIMACS TR: 2002-31

Tournaments that omit $N_5$ are well-quasi-ordered



Authors: Brenda J. Latka

ABSTRACT

The tournament $N_5$ can be obtained from the transitive tournament on $\{1,\ldots,5\}$, with the natural order, by reversing the edges between successive vertices. Tournaments that do {\em not} have $N_5$ as a subtournament are said to {\em omit} $N_5$. We describe the structure of tournaments that omit $N_5$ and use this with Kruskal's Tree Theorem to prove that this class of tournaments is well-quasi-ordered. The proof involves an encoding of the indecomposable tournaments omitting $N_5$ by a finite alphabet.

The main technical problem is giving an explicit description of the indecomposable tournaments omitting $N_5$. The key to the proof that the explicit description is complete is the observation that for any indecomposable tournament $T$ with $n>1$ vertices, there is a proper indecomposable subtournament of $T$ with $n-2$ or $n-1$ vertices. Thus the claim can be verified by a natural inductive procedure; it suffices to check that for any tournament $T$ in the explicitly given list, any indecomposable extension of $T$ by at most 2 vertices that omits $N_5$ will also be found in our list.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-31.ps.gz

DIMACS Home Page