Sumner's conjecture

Unsolved problem in mathematics

Does every $(2n-2)$-vertex tournament contain as a subgraph every $n$-vertex oriented tree?

More unsolved problems in mathematics

File:Polytrees in a tournament.svg

A 6-vertex tournament, and copies of every 4-vertex oriented tree within it.

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 $\lceil n-\frac{3}{2}\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

Rosenfeld (1972) 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 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.

References

• .
• . As cited by Wormald (1983).
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

External links

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