Sumner's conjecture

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 $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$, while the central vertex in $P$ has larger outdegree $n-1$.This example is from {{harvtxt|Kühn|Mycroft|Osthus|2011a}}. Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees.

However, in every tournament of $2n-2$ vertices, the average outdegree is $n-\backslash frac\{3\}\{2\}$, and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree $\backslash left\backslash lceil\; n-\backslash frac\{3\}\{2\}\backslash right\backslash rceil=n-1$, which can be used as the central vertex for a copy of $P$.

The following partial results on the conjecture have been proven.

• There is a function $f(n)$ with asymptotic growth rate $f(n)=2n+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)\backslash le\; 3n-3$.{{harvtxt|Kühn|Mycroft|Osthus|2011a}} and {{harvtxt|El Sahili|2004}}. For earlier weaker bounds on $f(n)$, see {{harvtxt|Chung|1981}}, {{harvtxt|Wormald|1983}}, {{harvtxt|Häggkvist|Thomason|1991}}, {{harvtxt|Havet|Thomassé|2000b}}, and {{harvtxt|Havet|2002}}.
• There is a function $g(k)$ such that tournaments on $n+g(k)$ vertices are universal for polytrees with $k$ leaves.{{harvtxt|Häggkvist|Thomason|1991}}; {{harvtxt|Havet|Thomassé|2000a}}; {{harvtxt|Havet|2002}}.
• There is a function $h(n,\backslash Delta)$ such that every $n$-vertex polytree with maximum degree at most $\backslash Delta$ forms a subgraph of every tournament with $h(n,\backslash Delta)$ vertices. When $\backslash Delta$ is a fixed constant, the asymptotic growth rate of $h(n,\backslash Delta)$ is $n+o(n)$.{{harvtxt|Kühn|Mycroft|Osthus|2011a}}.
• Every "near-regular" tournament on $2n-2$ vertices contains every $n$-vertex polytree.{{harvtxt|Reid|Wormald|1983}}.
• Every orientation of an $n$-vertex caterpillar tree with diameter at most four can be embedded as a subgraph of every $(2n-2)$-vertex tournament.
• Every $(2n-2)$-vertex tournament contains as a subgraph every $n$-vertex arborescence.{{harvtxt|Havet|Thomassé|2000b}}.

{{harvtxt|Rosenfeld|1972}} conjectured that every orientation of an $n$-vertex path graph (with $n\backslash ge\; 8$) can be embedded as a subgraph into every $n$-vertex tournament. After partial results by {{harvtxt|Thomason|1986}}, this was proven by {{harvtxt|Havet|Thomassé|2000a}}.

Havet and ThomasséIn {{harvtxt|Havet|2002}}, but jointly credited to Thomassé in that paper. 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 {{harvtxt|Naia|2018}}.

{{harvtxt|Burr|1980}} conjectured that, whenever a graph $G$ requires $2n-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.This is a corrected version of Burr's conjecture from {{harvtxt|Wormald|1983}}. As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of $n$ are universal for polytrees.

{{reflist|colwidth=30em}}

• {{citation

| last = Burr | first = Stefan A. | author-link = Stefan Burr

| contribution = Subtrees of directed graphs and hypergraphs

| series = Congressus Numerantium

| mr = 608430

| pages = 227–239

| title = Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I

| volume = 28

| year = 1980}}.

• {{citation

| last = Chung | first = F.R.K. | author-link = Fan Chung

| publisher = Bell Laboratories

| series = Internal Memorandum

| title = A note on subtrees in tournaments

| year = 1981}}. As cited by {{harvtxt|Wormald|1983}}.

• {{citation

| last = El Sahili | first = A.

| doi = 10.1016/j.jctb.2004.04.002

| issue = 1

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2078502

| pages = 183–187

| title = Trees in tournaments

| volume = 92

| year = 2004| doi-access = free

}}.

• {{citation

| last1 = Häggkvist | first1 = Roland

| last2 = Thomason | first2 = Andrew

| doi = 10.1007/BF01206356

| issue = 2

| journal = Combinatorica

| mr = 1136161

| pages = 123–130

| title = Trees in tournaments

| volume = 11

| year = 1991}}.

• {{citation

| last = Havet | first = Frédéric

| doi = 10.1016/S0012-365X(00)00463-5

| issue = 1–3

| journal = Discrete Mathematics

| mr = 1874730

| pages = 121–134

| title = Trees in tournaments

| volume = 243

| year = 2002| doi-access =

}}.

• {{citation

| last1 = Havet | first1 = Frédéric

| last2 = Thomassé | first2 = Stéphan

| doi = 10.1006/jctb.1999.1945

| issue = 2

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 1750898

| pages = 243–273

| title = Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture

| volume = 78

| year = 2000a| doi-access = free

}}.

• {{citation

| last1 = Havet | first1 = Frédéric

| last2 = Thomassé | first2 = Stéphan

| doi = 10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H

| issue = 4

| journal = Journal of Graph Theory

| mr = 1791347

| pages = 244–256

| title = Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture

| volume = 35

| year = 2000b}}.

• {{citation

| last1 = Kühn | first1 = Daniela | author1-link = Daniela Kühn

| last2 = Mycroft | first2 = Richard

| last3 = Osthus | first3 = Deryk

| doi = 10.1016/j.jctb.2010.12.006

| issue = 6

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 2832810 | zbl=1234.05115

| pages = 415–447

| title = An approximate version of Sumner's universal tournament conjecture

| volume = 101

| year = 2011a| arxiv = 1010.4429

}}.

• {{citation

| last1 = Kühn | first1 = Daniela | author1-link = Daniela Kühn

| last2 = Mycroft | first2 = Richard

| last3 = Osthus | first3 = Deryk

| arxiv = 1010.4430

| doi = 10.1112/plms/pdq035

| issue = 4

| journal = Proceedings of the London Mathematical Society | series = Third Series

| mr = 2793448 | zbl=1218.05034

| pages = 731–766

| title = A proof of Sumner's universal tournament conjecture for large tournaments

| volume = 102

| year = 2011b}}.

• {{citation

| last = Naia | first = Tássio

| type = Doctoral thesis

| publisher = University of Birmingham

| title = Large structures in dense directed graphs

| year=2018

| url = https://etheses.bham.ac.uk/id/eprint/8658/

}}.

• {{citation

| last1 = Reid | first1 = K. B.

| last2 = Wormald | first2 = N. C.

| issue = 2–4

| journal = Studia Scientiarum Mathematicarum Hungarica

| mr = 787942

| pages = 377–387

| title = Embedding oriented n-trees in tournaments

| volume = 18

| year = 1983}}.

• {{citation

| last = Rosenfeld | first = M.

| journal = Journal of Combinatorial Theory | series = Series B

| mr = 0285452

| pages = 93–99

| title = Antidirected Hamiltonian paths in tournaments

| volume = 12

| year = 1972

| doi=10.1016/0095-8956(72)90035-4| doi-access =

}}.

• {{citation

| last = Thomason | first = Andrew

| doi = 10.2307/2000567

| issue = 1

| journal = Transactions of the American Mathematical Society

| mr = 837805

| pages = 167–180

| title = Paths and cycles in tournaments

| volume = 296

| year = 1986| doi-access = free

| jstor = 2000567

}}.

• {{citation

| last = Wormald | first = Nicholas C.

| contribution = Subtrees of large tournaments

| doi = 10.1007/BFb0071535

| location = Berlin

| mr = 731598

| pages = 417–419

| publisher = Springer

| series = Lecture Notes in Math.

| title = Combinatorial mathematics, X (Adelaide, 1982)

| volume = 1036

| year = 1983| isbn = 978-3-540-12708-6

}}.

• [http://www.math.uiuc.edu/~west/openp/univtourn.html Sumner's Universal Tournament Conjecture (1971)], D. B. West, updated July 2008.

Category:Conjectures

Category:Unsolved problems in graph theory