pith. sign in

arxiv: 1609.03393 · v1 · pith:Y4OWMAHLnew · submitted 2016-09-12 · 🧮 math.CO

Unavoidable trees in tournaments

classification 🧮 math.CO
keywords unavoidableverticeseveryorientedcontainscopyprovetournament
0
0 comments X
read the original 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\"uhn, Mycroft and Osthus.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.