Sumner's conjecture

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

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.¹ 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.²

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}$.³ 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}$.

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}$.⁴
• There is a function ${\displaystyle g(k)}$ such that tournaments on ${\displaystyle n+g(k)}$ vertices are universal for polytrees with ${\displaystyle k}$ leaves.⁵
• 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)}$.⁶
• Every "near-regular" tournament on ${\displaystyle 2n-2}$ vertices contains every ${\displaystyle n}$-vertex polytree.⁷
• 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.⁷
• Every ${\displaystyle (2n-2)}$-vertex tournament contains as a subgraph every ${\displaystyle n}$-vertex arborescence.⁸

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.⁷ 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 ${\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.¹⁰ As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of ${\displaystyle n}$ are universal for polytrees.