# Sumner's conjecture

David Sumner (a graph theorist at the University of South Carolina) conjectured in 1971 that tournaments are universal graphs for polytrees. More precisely, **Sumner's conjecture** (also called **Sumner's universal tournament conjecture**) states that every orientation of every -vertex tree is a subgraph of every -vertex tournament.^{[1]} The conjecture remains unproven; Template:Harvtxt call it "one of the most well-known problems on tournaments."

## Examples

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

However, in every tournament of vertices, the average outdegree is , and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree , which can be used as the central vertex for a copy of .

## Partial results

The following partial results on the conjecture are known.

- It is true for all sufficiently large values of .
^{[3]} - There is a function with asymptotic growth rate with the property that every -vertex polytree can be embedded as a subgraph of every -vertex tournament. Additionally and more explicitly, .
^{[4]} - There is a function such that tournaments on vertices are universal for polytrees with leaves.
^{[5]} - There is a function such that every -vertex polytree with maximum degree at most forms a subgraph of every tournament with vertices. When is a fixed constant, the asymptotic growth rate of is .
^{[6]} - Every "near-regular" tournament on vertices contains every -vertex polytree.
^{[7]} - Every orientation of an -vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every -vertex tournament.
^{[7]} - Every -vertex tournament contains as a subgraph every -vertex rooted tree.
^{[8]}

## Related conjectures

Template:Harvtxt conjectured that every orientation of an -vertex path graph (with ) can be embedded as a subgraph into every -vertex tournament.^{[7]} After partial results by Template:Harvtxt this was proven by Template:Harvtxt.

Havet and Thomassé^{[9]} in turn conjectured a strengthening of Sumner's conjecture, that every tournament on vertices contains as a subgraph every polytree with at most leaves.

Template:Harvtxt conjectured that, whenever a graph requires or more colors in a coloring of , then every orientation of contains every orientation of an -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 are universal for polytrees.

## Notes

- ↑ Template:Harvtxt. However the earliest published citations given by Kühn et al. are to Template:Harvtxt and Template:Harvtxt. Template:Harvtxt cites the conjecture as an undated private communication by Sumner.
- ↑ This example is from Template:Harvtxt.
- ↑ Template:Harvtxt.
- ↑ Template:Harvtxt and Template:Harvtxt. For earlier weaker bounds on , see Template:Harvtxt, Template:Harvtxt, Template:Harvtxt, Template:Harvtxt, and Template:Harvtxt.
- ↑ Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
- ↑ Template:Harvtxt.
- ↑
^{7.0}^{7.1}^{7.2}Template:Harvtxt. - ↑ Template:Harvtxt.
- ↑ In Template:Harvtxt, but jointly credited to Thomassé in that paper.
- ↑ This is a corrected version of Burr's conjecture from Template:Harvtxt.

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}. As cited by Template:Harvtxt.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

## External links

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