Sumner's conjecture (also called Sumner's universal tournament conjecture) is a conjecture in extremal graph theory on oriented trees in tournaments. It states that every orientation of every n-vertex tree is a subgraph of every (2n-2)-vertex tournament. David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large n by Daniela Kühn, Richard Mycroft, and Deryk Osthus.

Examples

Let polytree P be a star K_{1,n-1}, in which all edges are oriented outward from the central vertex to the leaves. Then, P cannot be embedded in the tournament formed from the vertices of a regular 2n-3-gon by directing every edge clockwise around the polygon. For, in this tournament, every vertex has indegree and outdegree equal to n-2, while the central vertex in P has larger outdegree n-1. Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees. However, in every tournament of 2n-2 vertices, the average outdegree is, and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree, which can be used as the central vertex for a copy of P.

Partial results

The following partial results on the conjecture have been proven.

Related conjectures

conjectured that every orientation of an n-vertex path graph (with n\ge 8) can be embedded as a subgraph into every n-vertex tournament. After partial results by, this was proven by. Havet and Thomassé in turn conjectured a strengthening of Sumner's conjecture, that every tournament on n+k-1 vertices contains as a subgraph every polytree with at most k leaves. This has been confirmed for almost every tree by Mycroft and. conjectured that, whenever a graph G requires 2n-2 or more colors in a coloring of G, then every orientation of G contains every orientation of an n-vertex tree. Because complete graphs require a different color for each vertex, Sumner's conjecture would follow immediately from Burr's conjecture. As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of n are universal for polytrees.