An approximate version of Sumner's universal tournament conjecture

Abstract

Sumner's universal tournament conjecture states that any tournament on $2n-2$ vertices contains a copy of any directed tree on $n$ vertices. We prove an asymptotic version of this conjecture, namely that any tournament on $(2+o(1))n$ vertices contains a copy of any directed tree on $n$ vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed $\Delta$, any tournament on $(1+o(1))n$ vertices contains a copy of any directed tree on $n$ vertices with maximum degree at most $\Delta$.

36 pages

References in corpus (1)

• An exact minimum degree condition for Hamilton cycles in oriented graphs

Cited by in corpus (5)

• The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition
• The robust component structure of dense regular graphs and applications
• A survey on Hamilton cycles in directed graphs
• Cycle partitions of regular graphs
• Embedding spanning bipartite graphs of small bandwidth