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.
DIMACS Home Page