Unavoidable trees in tournaments | Zendy

Mycroft Richard | Zendy; Naia Tássio | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Unavoidable trees in tournaments

Author(s) -

Mycroft Richard,

Naia Tássio

Publication year - 2018

Publication title -

random structures and algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.314

H-Index - 69

eISSN - 1098-2418

pISSN - 1042-9832

DOI - 10.1002/rsa.20765

Subject(s) - tournament , combinatorics , conjecture , mathematics , tree (set theory) , degree (music) , discrete mathematics , physics , acoustics

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research