Unavoidable trees in tournaments
Research output: Contribution to journal › Article
Authors
Colleges, School and Institutes
Abstract
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.
Details
| Original language | English |
|---|---|
| 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 |