Unavoidable trees in tournaments. Issue 2 (9th February 2018)

• Record Type: Journal Article
• Authors: Mycroft, Richard; Naia, Tássio
• Is Part Of: Random structures & algorithms. Volume 53:Issue 2(2018)
• Page Start: 352
• Page End: 385
• Publication Date: 2018-02-09
• Subjects: directed graphs -- tournaments -- trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20765
• Languages: English
• ISSNs: 1042-9832

Abstract

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 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 Kühn, Mycroft, and Osthus.