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 ${\displaystyle n}$-vertex tree is a subgraph of every ${\displaystyle (2n-2)}$-vertex tournament.^[1] 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 ${\displaystyle n}$ by Daniela Kühn, Richard Mycroft, and Deryk Osthus.^[2]

Unsolved problem in mathematics

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

More unsolved problems in mathematics

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

Examples

Let polytree ${\displaystyle P}$ be a star ${\displaystyle K_{1,n-1}}$, in which all edges are oriented outward from the central vertex to the leaves. Then, ${\displaystyle P}$ cannot be embedded in the tournament formed from the vertices of a regular ${\displaystyle 2n-3}$-gon by directing every edge clockwise around the polygon. For, in this tournament, every vertex has indegree and outdegree equal to ${\displaystyle n-2}$, while the central vertex in ${\displaystyle P}$ has larger outdegree ${\displaystyle n-1}$.^[3] Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees.

However, in every tournament of ${\displaystyle 2n-2}$ vertices, the average outdegree is ${\displaystyle 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 ${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$, which can be used as the central vertex for a copy of ${\displaystyle P}$.

Partial results

The following partial results on the conjecture have been proven.

• There is a function ${\displaystyle f(n)}$ with asymptotic growth rate ${\displaystyle f(n)=2n+o(n)}$ with the property that every ${\displaystyle n}$-vertex polytree can be embedded as a subgraph of every ${\displaystyle f(n)}$-vertex tournament. Additionally and more explicitly, ${\displaystyle f(n)\leq 3n-3}$.^[4]
• There is a function ${\displaystyle g(k)}$ such that tournaments on ${\displaystyle n+g(k)}$ vertices are universal for polytrees with ${\displaystyle k}$ leaves.^[5]
• There is a function ${\displaystyle h(n,\Delta )}$ such that every ${\displaystyle n}$-vertex polytree with maximum degree at most ${\displaystyle \Delta }$ forms a subgraph of every tournament with ${\displaystyle h(n,\Delta )}$ vertices. When ${\displaystyle \Delta }$ is a fixed constant, the asymptotic growth rate of ${\displaystyle h(n,\Delta )}$ is ${\displaystyle n+o(n)}$.^[6]
• Every "near-regular" tournament on ${\displaystyle 2n-2}$ vertices contains every ${\displaystyle n}$-vertex polytree.^[7]
• Every orientation of an ${\displaystyle n}$-vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every ${\displaystyle (2n-2)}$-vertex tournament.^[7]
• Every ${\displaystyle (2n-2)}$-vertex tournament contains as a subgraph every ${\displaystyle n}$-vertex arborescence.^[8]

Related conjectures

Rosenfeld (1972) conjectured that every orientation of an ${\displaystyle n}$-vertex path graph (with ${\displaystyle n\geq 8}$) can be embedded as a subgraph into every ${\displaystyle n}$-vertex tournament.^[7] After partial results by Thomason (1986), this was proven by Havet & Thomassé (2000a).

Havet and Thomassé^[9] in turn conjectured a strengthening of Sumner's conjecture, that every tournament on ${\displaystyle n+k-1}$ vertices contains as a subgraph every polytree with at most ${\displaystyle k}$ leaves. This has been confirmed for almost every tree by Mycroft and Naia (2018).

Burr (1980) conjectured that, whenever a graph ${\displaystyle G}$ requires ${\displaystyle 2n-2}$ or more colors in a coloring of ${\displaystyle G}$, then every orientation of ${\displaystyle G}$ contains every orientation of an ${\displaystyle 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 ${\displaystyle n}$ are universal for polytrees.