Unavoidable trees in tournaments
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
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.
|Number of pages||29|
|Journal||Random Structures and Algorithms|
|Early online date||9 Feb 2018|
|Publication status||E-pub ahead of print - 9 Feb 2018|