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 |
|
|