# Sumner's conjecture

$(2n-2)$
$n$
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 $n-{\frac {3}{2}}$, and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree $\left\lceil n-{\frac {3}{2}}\right\rceil =n-1$, 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.
* There is a function $f(n)$ with asymptotic growth rate $f(n)=2n+o(n)$ with the property that every $n$-vertex polytree can be embedded as a subgraph of every $f(n)$-vertex tournament. Additionally and more explicitly, $f(n)\leq 3n-3$.
* There is a function $g(k)$ such that tournaments on $n+g(k)$ vertices are universal for polytrees with $k$ leaves.
* There is a function $h(n,\Delta )$ such that every $n$-vertex polytree with maximum degree at most $\Delta$ forms a subgraph of every tournament with $h(n,\Delta )$ vertices. When $\Delta$ is a fixed constant, the asymptotic growth rate of $h(n,\Delta )$ is $n+o(n)$.
* Every "near-regular" tournament on $2n-2$ vertices contains every $n$-vertex polytree.
* Every orientation of an $n$-vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every $(2n-2)$-vertex tournament.
* Every $(2n-2)$-vertex tournament contains as a subgraph every $n$-vertex arborescence.

## Related conjectures

Rosenfeld (1972) conjectured that every orientation of an $n$-vertex path graph (with $n\geq 8$) can be embedded as a subgraph into every $n$-vertex tournament. After partial results by Thomason (1986), this was proven by Havet & Thomassé (2000a).
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 Naia (2018).
Burr (1980) 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.