Unavoidable trees in tournaments

作者：Mycroft Richard^*; Naia Tassio

来源：Random Structures and Algorithms, 2018, 53(2): 352-385.

DOI：10.1002/rsa.20765

• directed graphs
• tournaments
• trees

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 labeled 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 Kuhn, Mycroft, and Osthus.

• 出版日期2018-9