Sumner's Conjecture

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_$, 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$, 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\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)\le 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

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.This is a corrected version of Burr's conjecture from . As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of $n$ are universal for polytrees.

Notes

References

*.
*. As cited by .
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*{{citation
, last = Wormald , first = Nicholas C.
, contribution = Subtrees of large tournaments
, doi = 10.1007/BFb0071535
, location = Berlin
, mr = 731598
, pages = 417–419
, publisher = Springer
, series = Lecture Notes in Math.
, title = Combinatorial mathematics, X (Adelaide, 1982)
, volume = 1036
, year = 1983, isbn = 978-3-540-12708-6
.

External links

Sumner's Universal Tournament Conjecture (1971)
D. B. West, updated July 2008.

Conjectures
Unsolved problems in graph theory