# A proof of Sumner's universal tournament conjecture for large tournaments

@article{Kuhn2011APO, title={A proof of Sumner's universal tournament conjecture for large tournaments}, author={Daniel Kuhn and Richard Mycroft and Deryk Osthus}, journal={Proceedings of The London Mathematical Society}, year={2011}, volume={102}, pages={731-766} }

Sumner's universal tournament conjecture states that any tournament on $2n-2$ vertices contains any directed tree on $n$ vertices. In this paper we prove that this conjecture holds for all sufficiently large $n$. The proof makes extensive use of results and ideas from a recent paper by the same authors, in which an approximate version of the conjecture was proved.

#### 18 Citations

An approximate version of Sumnerʼs universal tournament conjecture

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2011

An asymptotically best possible result is proved that for any fixed @D, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most @D. Expand

Unavoidable trees in tournaments

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2018

This paper gives a sufficient condition for an oriented tree T to be unavoidable, and uses this to prove that almost all labelled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. Expand

Trees with Few Leaves in Tournaments

- Mathematics
- 2021

We prove that there exists C > 0 such that any (n+Ck)-vertex tournament contains a copy of every n-vertex oriented tree with k leaves, improving the previously best known bound of n+O(k) vertices to… Expand

A Ramsey type result for oriented trees

- Computer Science, Mathematics
- Eur. J. Comb.
- 2017

It is proved that r ( h , k ) = ( h − 1 ) k for all k sufficiently large ( k = Θ ( h log h ) suffices) and the bound ( h-1 ) k is tight. Expand

Robust expansion and Hamiltonicity

- Mathematics
- 2015

This thesis contains four results in extremal graph theory relating to the recent notion of robust expansion, and the classical notion of Hamiltonicity. In Chapter 2 we prove that every sufficiently… Expand

Tournaments and Semicomplete Digraphs

- Mathematics, Computer Science
- Classes of Directed Graphs
- 2018

This chapter covers a very broad range of results on tournaments and semicomplete digraphs from classical to very recent ones and gives a number of proofs which illustrate the diversity of proof techniques that have been applied. Expand

An Extension of the Hajnal–Szemerédi Theorem to Directed Graphs

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2014

This work shows that every directed graph with |G| = ks and δ(G)⩾ k(s − 1) contains k disjoint s-cliques; moreover this degree bound is optimal; and makes some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. Expand

The regularity method in directed graphs and hypergraphs

- Mathematics
- 2010

In recent years the regularity method has been used to tackle many embedding problems in extremal graph theory. This thesis demonstrates and develops three different techniques which can be used in… Expand

Directed Ramsey number for trees

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2019

It is proved that r → ( T, k ) ≤ c k | T | k for any oriented tree T, which is a generalisation of a similar result for directed paths by Chvatal and by Gyarfas and Lehel, and answers a question of Yuster. Expand

The robust component structure of dense regular graphs and applications

- Mathematics
- 2015

In this paper, we study the large-scale structure of dense regular graphs. This involves the notion of robust expansion, a recent concept which has already been used successfully to settle several… Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

An approximate version of Sumnerʼs universal tournament conjecture

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2011

An asymptotically best possible result is proved that for any fixed @D, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most @D. Expand

Trees in tournaments

- Mathematics
- 2004

In 1971, Sumner conjectured that any tournament of order 2(n - 1) contains any oriented tree of order n. Since then several bounds have been established that get closer and closer to the suggested… Expand

Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2000

It is proved that with three exceptions, every tournament of order n contains each oriented path of order g, which is equivalent to n ≥1. Expand

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

- Mathematics
- 2000

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such… Expand

Subtrees of large tournaments

- Mathematics
- 1983

By an oriented graph we mean a graph in which each edge has been directed. A tournament is an oriented complete graph. Let f(n) by the least integer for which every tournament on f(n) vertices… Expand

Surveys in Combinatorics 2009: Embedding large subgraphs into dense graphs

- Mathematics
- 2009

What conditions ensure that a graph G contains some given spanning subgraph H? The most famous examples of results of this kind are probably Dirac's theorem on Hamilton cycles and Tutte's theorem on… Expand

Paths and cycles in tournaments

- Mathematics
- 1986

Sufficient conditions are given for the existence of an oriented path with given end vertices in a tournament. As a consequence a conjecture of Rosenfeld is established. This states that if n is… Expand

On Unavoidability of Trees with k Leaves

- Mathematics, Computer Science
- Graphs Comb.
- 2003

Havet and Thomassé's conjecture is proved to be true for constructible trees: g(k) is the smallest integer such that every oriented tree of order n with k leaves is (n+g(k)) -unavoidable. Expand

Hamiltonian degree sequences in digraphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2010

We show that for each @h>0 every digraph G of sufficiently large order n is Hamiltonian if its out- and indegree sequences d"1^+= =n-i and (ii) d"i^->=i+@hn or d"n"-"i"-"@h"n^+>=n-i for all i

Trees with three leaves are (n+1)-unavoidable

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2004

It is proved that every tree A with three leaves of order n is contained in every tournament T oforder n + 1 except if (T;A) is (R5;S3+) or its dual, where R5 is the regular tournament on five vertices and S3- is the outstar of degree three. Expand