Get Sumner's Conjecture essential facts below. View Videos or join the Sumner's Conjecture discussion. Add Sumner's Conjecture to your PopFlock.com topic list for future reference or share this resource on social media.
Sumner's Conjecture
Unsolved problem in mathematics:
Does every $(2n-2)$-vertex tournament contain as a subgraph every $n$-vertex oriented tree?
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$.^{[2]} 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 are known.
It is true for all sufficiently large values of $n$.^{[3]}
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$.^{[4]}
There is a function $g(k)$ such that tournaments on $n+g(k)$ vertices are universal for polytrees with $k$ leaves.^{[5]}
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)$.^{[6]}
Every "near-regular" tournament on $2n-2$ vertices contains every $n$-vertex polytree.^{[7]}
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.^{[7]}
Every $(2n-2)$-vertex tournament contains as a subgraph every $n$-vertex arborescence.^{[8]}
Havet and Thomassé^{[9]} 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.^{[10]} As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of $n$ are universal for polytrees.
^In Havet (2002), but jointly credited to Thomassé in that paper.
^This is a corrected version of Burr's conjecture from Wormald (1983).
References
Burr, Stefan A. (1980), "Subtrees of directed graphs and hypergraphs", Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I, Congressus Numerantium, 28, pp. 227-239, MR0608430.
Reid, K. B.; Wormald, N. C. (1983), "Embedding oriented n-trees in tournaments", Studia Scientiarum Mathematicarum Hungarica, 18 (2-4): 377-387, MR0787942.
Thomason, Andrew (1986), "Paths and cycles in tournaments", Transactions of the American Mathematical Society, 296 (1): 167-180, doi:10.2307/2000567, MR0837805.
Wormald, Nicholas C. (1983), "Subtrees of large tournaments", Combinatorial mathematics, X (Adelaide, 1982), Lecture Notes in Math., 1036, Berlin: Springer, pp. 417-419, doi:10.1007/BFb0071535, MR0731598.