Structure theorem for tournaments excluding U 5
Gaku Liu · arXiv (Cornell University) · 2012
Let U5 be the tournament with vertices v1,...,v5 such that v2 → v1, and vi → vj if j − i ≡ 1, 2 (mod 5) and {i,j} 6 {1,2}. In this paper we describe the tournaments which do not have U5 as a subtournament. Specifically, we show that if a tournament G is “prime”—that is, if there is no subset X ⊆ V (G), 1 < |X| < |V (G)|, such that for all v ∈ V (G)\X, either v → x for all x ∈ X or x → v for all x ∈ X—then G excludes U5 if and only if either G is a specific tournament Tn or V (G) can be partitioned into sets X, Y , Z such that X ∪ Y , Y ∪ Z, and Z ∪ X are transitive. From the prime tournaments that exclude U5 we can construct all the tournaments which exclude U5.