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