**Originator:** David Sumner (University of South Carolina)

**Definitions:**
An *oriented tree* is a digraph that is an orientation of a tree.
A *branching* is an oriented tree that has contains paths from one vertex
to all other vertices.

**Conjecture:**
For *n > 1*, every tournament of order *2n-2* contains every oriented
tree of order *n*.

**Comments:**
Reid and Wormald [RW] proved that near-regular tournaments of this order
contain all oriented trees. On the other hand, Havet and Thomassé [HT2]
proved that every tournament with *2n-2* vertices contains every branching
with *n* vertices.

When all tournaments must contain all oriented *n*-vertex trees, a
succession of papers has improved the upper bound on the number of vertices
that suffice. Wormald [W] showed that *n*lg*(2n/e)* vertices suffice.
Häggkvist and Thomason [HT1] proved that *12n* and asymptotically
*(4+o(1))n* vertices suffice. Havet [H] used their method to improve it
to *7.6n*. Havet and Thomassá [HT2] then improved the bound to
*(7n-5)/2* using median orders, where a *median order* of a
tournament *T* is a transitive tournament on *V(T)* having the most
edges in common with *T*. Finally, El Sahili [E] further pursued the
use of median orders to prove that every tournament with *3n-3* vertices
contains every oriented tree with *n* vertices. (Thanks to Kunal Dutta
for communicating these results.)

More recently, Tássio Naia communicated that the conjecture has been proved for all sufficiently large tournaments by Kühn, Mycroft and Osthus [KMO].

**References:**

[E] A. El Sahili, Trees in tournaments.
J. Combin. Theory Ser. B 92 (2004), no. 1, 183--187.

[HT1] R. Häggkvist, A.G. Thomason, Trees in tournaments, Combinatorica 11
(1991) 123--130.

[H] F. Havet, Trees in tournaments, J. Discrete Math. 243 (1--3) (2002)
121--134.

[HT2] F. Havet, S. Thomassé, Median orders of tournaments: a tool for
the second # neighborhood problem and Sumner's conjecture, J. Graph Theory 35
(2000) 244--256.

[KMO] D. Kühn, R. Mycroft, and D. Osthus, A proof of Sumner's universal
tournament conjecture for large tournaments, http://arxiv.org/abs/1010.4430.

[RW] K.B. Reid, N.C. Wormald, Stud. Sci. Math. Hungaria 18 (1983) 377--387.

[W] N.C. Wormald, Subtrees of large tournaments, in: Combinatorial Mathematics,
X (Adelaide, 1982). Lecture Notes in Mathematics, Vol. 1036, Springer, Berlin,
1983, 417--419.

Updated 7/09/2008