Structure theorem for U5-free tournaments

Abstract

Let $U_5$ be the tournament with vertices $v_1$, ..., $v_5$ such that $v_2\to v_1$, and $v_i\to v_j$ if $j-i\equiv 1$, $2(\mathrm{mod}5)$ and $i,j\ne 1,2$. In this paper we describe the tournaments which do not have $U_5$ as a subtournament. Specifically, we show that if a tournament $G$ is "prime"---that is, if there is no subset $X\subseteq V(G)$, $1<|X|<|V(G)|$, such that for all $v\in V(G)\backslash X$, either $v\to x$ for all $x\in X$ or $x\to v$ for all $x\in X$---then $G$ is $U_5$-free if and only if either $G$ is a specific tournament $T_n$ or $V(G)$ can be partitioned into sets $X$, $Y$, $Z$ such that $X\cup Y$, $Y\cup Z$, and $Z\cup X$ are transitive. From the prime $U_5$-free tournaments we can construct all the $U_5$-free tournaments. We use the theorem to show that every $U_5$-free tournament with $n$ vertices has a transitive subtournament with at least $n^{{\log }_{3}2}$ vertices, and that this bound is tight.

arXiv comment15 pages, 1 figure. Changes from previous version: Added a section; added the definitions of v, A, and B to the main proof; general edits

Cited by in corpus (1)

• Unavoidable Subtournaments in Tournaments with Large Chromatic Number