2016/09/12 by Mycroft, Richard, Naia, Tássio
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1609.03393
An oriented tree T on n vertices is unavoidable if every tournament on n vertices contains a copy of T. In this paper we give a sufficient condition for T to be unavoidable, and use this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on n + o(n) vertices contains a copy of every oriented tree T on n vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft and Osthus.