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 {\displaystyle n} -vertex tree is a subgraph of every ( 2 n − 2 ) {\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 n {\displaystyle n} by Daniela Kühn, Richard Mycroft, and Deryk Osthus.
Examples Let polytree P {\displaystyle P} be a star K 1 , n − 1 {\displaystyle K_{1,n-1}} , in which all edges are oriented outward from the central vertex to the leaves. Then, P {\displaystyle P} cannot be embedded in the tournament formed from the vertices of a regular 2 n − 3 {\displaystyle 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 {\displaystyle n-2} , while the central vertex in P {\displaystyle P} has larger outdegree n − 1 {\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 2 n − 2 {\displaystyle 2n-2} vertices, the average outdegree is n − 3 2 {\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 ⌈ n − 3 2 ⌉ = n − 1 {\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1} , which can be used as the central vertex for a copy of P {\displaystyle P} .
Partial results The following partial results on the conjecture have been proven.
There is a function f ( n ) {\displaystyle f(n)} with asymptotic growth rate f ( n ) = 2 n + o ( n ) {\displaystyle f(n)=2n+o(n)} with the property that every n {\displaystyle n} -vertex polytree can be embedded as a subgraph of every f ( n ) {\displaystyle f(n)} -vertex tournament. Additionally and more explicitly, f ( n ) ≤ 3 n − 3 {\displaystyle f(n)\leq 3n-3} . There is a function g ( k ) {\displaystyle g(k)} such that tournaments on n + g ( k ) {\displaystyle n+g(k)} vertices are universal for polytrees with k {\displaystyle k} leaves. There is a function h ( n , Δ ) {\displaystyle h(n,\Delta )} such that every n {\displaystyle n} -vertex polytree with maximum degree at most Δ {\displaystyle \Delta } forms a subgraph of every tournament with h ( n , Δ ) {\displaystyle h(n,\Delta )} vertices. When Δ {\displaystyle \Delta } is a fixed constant, the asymptotic growth rate of h ( n , Δ ) {\displaystyle h(n,\Delta )} is n + o ( n ) {\displaystyle n+o(n)} . Every "near-regular" tournament on 2 n − 2 {\displaystyle 2n-2} vertices contains every n {\displaystyle n} -vertex polytree. Every orientation of an n {\displaystyle n} -vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every ( 2 n − 2 ) {\displaystyle (2n-2)} -vertex tournament. Every ( 2 n − 2 ) {\displaystyle (2n-2)} -vertex tournament contains as a subgraph every n {\displaystyle n} -vertex arborescence.
… excerpt ends here. Continue reading the full article.
