Unavoidable trees in tournaments

DOI10.1002/RSA.20765MaRDI QIDQ4684833zbMATH OpenOpenAlexFDO

Authors Richard Mycroft, Tássio Naia

Publication date 25 September 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.03393, https://research.birmingham.ac.uk/portal/en/publications/unavoidable-trees-in-tournaments(f2723085-db44-4c0e-8c31-8c7402664c5b).html

zbMATH Keywords

directed graphstournamentstrees

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20)

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.

Recommendations

• Trees in tournaments
• On the unavoidability of oriented trees
• Trees in tournaments
• Trees with three leaves are (n+1)-unavoidable
• scientific article; zbMATH DE number 3902685

Cited in

(15)

• Trees with three leaves are (\(n+1\))-unavoidable
• Unavoidable subtrees
• Trees with few leaves in tournaments
• Spanning trees of dense directed graphs
• Trees contained in every orientation of a graph
• Trees with three leaves are (n+1)-unavoidable
• Trees in tournaments
• Large unavoidable subtournaments
• Orientation Ramsey thresholds for cycles and cliques
• On the unavoidability of oriented trees
• On the unavoidability of oriented trees
• Trees in tournaments
• Trees with many leaves in tournaments
• Directed graphs with lower orientation Ramsey thresholds
• Unavoidable tournaments

This page was built for publication: Unavoidable trees in tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4684833)