Sumner's conjecture explained

Sumner's conjecture (also called Sumner's universal tournament conjecture) states that every orientation of every

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

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 2 n -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 .^[3] 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 vertices, the average outdegree is n - (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 - (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 have been proven.

• There is a function

f(n) with asymptotic growth rate f(n) =2 n + 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 3 n -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

2 n -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 ( 2 n -2 ) -vertex tournament.^[7]

• Every

( 2 n -2 ) -vertex tournament contains as a subgraph every n -vertex arborescence.^[8]

Related conjectures

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.^[7] After partial results by, this was proven by .

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 .

conjectured that, whenever a graph

G requires 2 n -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.

References

• .
• . As cited by .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .

External links

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

Notes and References

1. . However the earliest published citations given by Kühn et al. are to and . cites the conjecture as an undated private communication by Sumner.
2. .
3. This example is from .
4. and . For earlier weaker bounds on f(n) , see,,,, and .

5. ; .

6. .
7. .
8. .
9. In, but jointly credited to Thomassé in that paper.
10. This is a corrected version of Burr's conjecture from .