An approximate version of Sumnerʼs universal tournament conjecture

Sumnerʼs universal tournament conjecture states that any tournament on 2 n − 2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on ( 2 + o ( 1 ) ) n vertices contains a copy of any directed tree on n vertices....

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial theory. Series B 2011-11, Vol.101 (6), p.415-447
Main Authors: Kühn, Daniela, Mycroft, Richard, Osthus, Deryk
Format: Article
Language:English
Subjects:
Digraphs
Regularity lemma
Tournaments
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Sumnerʼs universal tournament conjecture states that any tournament on 2 n − 2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on ( 2 + o ( 1 ) ) n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on ( 1 + o ( 1 ) ) n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.
ISSN:0095-8956
1096-0902
DOI:10.1016/j.jctb.2010.12.006