An improved finite bound for oriented trees in tournaments

Abstract

Sumner's universal tournament conjecture asserts that every tournament on $2n-2$ vertices contains every oriented tree on $n$ vertices. Let $f(n)$ be the least integer $N$ such that every tournament on $N$ vertices contains every oriented tree on $n$ vertices. Havet and Thomassé proved that $f(n)\le \lceil (7n-5)/2\rceil$, El Sahili improved this to $f(n)\le 3n-3$, and Dross and Havet subsequently obtained $f(n)\le \lceil 21n/8-47/16\rceil$. We refine their median-order method. More precisely, every non-bi-arborescence on $n$ vertices with $k$ leaves is $(4n-2k-4)$-unavoidable, which strictly improves their many-leaf estimate; bi-arborescences satisfy the stronger bound $2n-2$. Combining this refinement with their few-leaf bound gives $f(n)\le \lceil (18n-23)/7\rceil$ for every $n\ge 2$. Thus the coefficient in the previously best general bound valid uniformly for all $n$ is reduced from $21/8$ to $18/7$.