Sumner's Universal Tournament Conjecture (1971)

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 nlg(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].

[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,
[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.

Back to Index Page Link to Glossary

Updated 7/09/2008