Unavoidable trees in tournaments

Research output: Contribution to journalArticle

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 languageEnglish
Number of pages29
JournalRandom Structures and Algorithms
Early online date9 Feb 2018
Publication statusE-pub ahead of print - 9 Feb 2018