DIMACS TR: 2002-24
A Classification of Antichains of Finite Tournaments
Authors: Brenda J. Latka
ABSTRACT
Tournament embedding is an order relation on the class of finite
tournaments. An antichain is a set of finite tournaments that are pairwise
incomparable in this ordering. We say an antichain ${\cal A}$ can be
extended to an antichain ${\cal B}$ if ${\cal A}\subseteq {\cal B}$.
Those finite antichains that can not be extended to antichains
of arbitrarily large finite cardinality are exactly those that
contain a member of each of four families of tournaments. We give an
upper bound on the cardinality of extensions of such antichains. This
bound
depends on
the maximum order of the tournaments in the antichain.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-24.ps.gz
DIMACS Home Page