Unavoidable trees in tournaments

Richard Mycroft; Tássio Naia Dos Santos

doi:10.1002/rsa.20765

Unavoidable trees in tournaments

Richard Mycroft, Tássio Naia Dos Santos

Mathematics

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

211 Downloads (Pure)

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

Original language	English
Number of pages	29
Journal	Random Structures and Algorithms
Early online date	9 Feb 2018
DOIs	https://doi.org/10.1002/rsa.20765
Publication status	E-pub ahead of print - 9 Feb 2018

Access to Document

10.1002/rsa.20765

Mycroft_&_Naia_Unavoidable_trees_in_tournaments_Random_Structures_and_Algorihtms_2018
Checked for Eligibility: 15/01/2018 This is the peer reviewed version of the following article: Mycroft R, Naia T. Unavoidable trees in tournaments. Random Struct Alg., which has been published in final form at: https://doi.org/10.1002/rsa.20765. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.
Accepted author manuscript, 615 KBLicence: None: All rights reserved

https://arxiv.org/pdf/1609.03393.pdf

Embeddings in hypergraphs
Mycroft, R. (Principal Investigator)
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils

Cite this

@article{f2723085db444c0e8c318c7402664c5b,

title = "Unavoidable trees in tournaments",

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{\"u}hn, Mycroft and Osthus.",

author = "Richard Mycroft and {Naia Dos Santos}, T{\'a}ssio",

year = "2018",

month = feb,

day = "9",

doi = "10.1002/rsa.20765",

language = "English",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

}

TY - JOUR

T1 - Unavoidable trees in tournaments

AU - Mycroft, Richard

AU - Naia Dos Santos, Tássio

PY - 2018/2/9

Y1 - 2018/2/9

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

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

U2 - 10.1002/rsa.20765

DO - 10.1002/rsa.20765

M3 - Article

SN - 1042-9832

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

ER -

Unavoidable trees in tournaments

Abstract

Access to Document

Fingerprint

Projects

Embeddings in hypergraphs

Cite this