Structure Theorem for U5‐free Tournaments |
| |
| Authors: | Gaku Liu |
| |
| Affiliation: | DEPARTMENT OF MATHEMATICS, MASSACHUSETTS INSTITUTE OF TECHNOLOGY, CAMBRIDGE, MA |
| |
| Abstract: | Let U5 be the tournament with vertices v1, …, v5 such that  , and  if  ,  and  . In this article, we describe the tournaments that do not have U5 as a subtournament. Specifically, we show that if a tournament G is “prime”—that is, if there is no subset  ,  , such that for all  , either  for all  or  for all  —then G is U5‐free if and only if either G is a specific tournament  or  can be partitioned into sets X, Y, Z such that  ,  , and  are transitive. From the prime U5‐free tournaments we can construct all the U5‐free tournaments. We use the theorem to show that every U5‐free tournament with n vertices has a transitive subtournament with at least  vertices, and that this bound is tight. |
| |
| Keywords: | tournament structure theorem transitive tournament prime tournament |
|
|
