Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Sumner's conjecture
Unsolved problem in mathematics Does every ( 2 n − 2 ) {\displaystyle (2n-2)} -vertex tournament contain as a subgraph every n {\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 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.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Sumner's conjecture yet.
We don't have any PDF documents related to Sumner's conjecture yet.
We don't have any Books related to Sumner's conjecture yet.
We don't have any archived web articles related to Sumner's conjecture yet.

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} .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 {\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} .4
  • 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.5
  • 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)} .6
  • Every "near-regular" tournament on 2 n − 2 {\displaystyle 2n-2} vertices contains every n {\displaystyle n} -vertex polytree.7
  • 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.8
  • Every ( 2 n − 2 ) {\displaystyle (2n-2)} -vertex tournament contains as a subgraph every n {\displaystyle n} -vertex arborescence.9

Rosenfeld (1972) conjectured that every orientation of an n {\displaystyle n} -vertex path graph (with n ≥ 8 {\displaystyle n\geq 8} ) can be embedded as a subgraph into every n {\displaystyle n} -vertex tournament.10 After partial results by Thomason (1986), this was proven by Havet & Thomassé (2000a).

Havet and Thomassé11 in turn conjectured a strengthening of Sumner's conjecture, that every tournament on n + k − 1 {\displaystyle n+k-1} vertices contains as a subgraph every polytree with at most k {\displaystyle k} leaves. This has been confirmed for almost every tree by Mycroft and Naia (2018).

Burr (1980) conjectured that, whenever a graph G {\displaystyle G} requires 2 n − 2 {\displaystyle 2n-2} or more colors in a coloring of G {\displaystyle G} , then every orientation of G {\displaystyle G} contains every orientation of an n {\displaystyle n} -vertex tree. Because complete graphs require a different color for each vertex, Sumner's conjecture would follow immediately from Burr's conjecture.12 As Burr showed, orientations of graphs whose chromatic number grows quadratically as a function of n {\displaystyle n} are universal for polytrees.

Notes

References

  1. Kühn, Mycroft & Osthus (2011a). However the earliest published citations given by Kühn et al. are to Reid & Wormald (1983) and Wormald (1983). Wormald (1983) cites the conjecture as an undated private communication by Sumner. - Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011a), "An approximate version of Sumner's universal tournament conjecture", Journal of Combinatorial Theory, Series B, 101 (6): 415–447, arXiv:1010.4429, doi:10.1016/j.jctb.2010.12.006, MR 2832810, Zbl 1234.05115 https://arxiv.org/abs/1010.4429 ↩

  2. Kühn, Mycroft & Osthus (2011b). - Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011b), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society, Third Series, 102 (4): 731–766, arXiv:1010.4430, doi:10.1112/plms/pdq035, MR 2793448, Zbl 1218.05034 https://arxiv.org/abs/1010.4430 ↩

  3. This example is from Kühn, Mycroft & Osthus (2011a). - Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011a), "An approximate version of Sumner's universal tournament conjecture", Journal of Combinatorial Theory, Series B, 101 (6): 415–447, arXiv:1010.4429, doi:10.1016/j.jctb.2010.12.006, MR 2832810, Zbl 1234.05115 https://arxiv.org/abs/1010.4429 ↩

  4. Kühn, Mycroft & Osthus (2011a) and El Sahili (2004). For earlier weaker bounds on f ( n ) {\displaystyle f(n)} , see Chung (1981), Wormald (1983), Häggkvist & Thomason (1991), Havet & Thomassé (2000b), and Havet (2002). - Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011a), "An approximate version of Sumner's universal tournament conjecture", Journal of Combinatorial Theory, Series B, 101 (6): 415–447, arXiv:1010.4429, doi:10.1016/j.jctb.2010.12.006, MR 2832810, Zbl 1234.05115 https://arxiv.org/abs/1010.4429 ↩

  5. Häggkvist & Thomason (1991); Havet & Thomassé (2000a); Havet (2002). - Häggkvist, Roland; Thomason, Andrew (1991), "Trees in tournaments", Combinatorica, 11 (2): 123–130, doi:10.1007/BF01206356, MR 1136161 https://doi.org/10.1007%2FBF01206356 ↩

  6. Kühn, Mycroft & Osthus (2011a). - Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011a), "An approximate version of Sumner's universal tournament conjecture", Journal of Combinatorial Theory, Series B, 101 (6): 415–447, arXiv:1010.4429, doi:10.1016/j.jctb.2010.12.006, MR 2832810, Zbl 1234.05115 https://arxiv.org/abs/1010.4429 ↩

  7. Reid & Wormald (1983). - Reid, K. B.; Wormald, N. C. (1983), "Embedding oriented n-trees in tournaments", Studia Scientiarum Mathematicarum Hungarica, 18 (2–4): 377–387, MR 0787942 https://mathscinet.ams.org/mathscinet-getitem?mr=0787942 ↩

  8. Reid & Wormald (1983). - Reid, K. B.; Wormald, N. C. (1983), "Embedding oriented n-trees in tournaments", Studia Scientiarum Mathematicarum Hungarica, 18 (2–4): 377–387, MR 0787942 https://mathscinet.ams.org/mathscinet-getitem?mr=0787942 ↩

  9. Havet & Thomassé (2000b). - Havet, Frédéric; Thomassé, Stéphan (2000b), "Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture", Journal of Graph Theory, 35 (4): 244–256, doi:10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H, MR 1791347 https://doi.org/10.1002%2F1097-0118%28200012%2935%3A4%3C244%3A%3AAID-JGT2%3E3.0.CO%3B2-H ↩

  10. Reid & Wormald (1983). - Reid, K. B.; Wormald, N. C. (1983), "Embedding oriented n-trees in tournaments", Studia Scientiarum Mathematicarum Hungarica, 18 (2–4): 377–387, MR 0787942 https://mathscinet.ams.org/mathscinet-getitem?mr=0787942 ↩

  11. In Havet (2002), but jointly credited to Thomassé in that paper. - Havet, Frédéric (2002), "Trees in tournaments", Discrete Mathematics, 243 (1–3): 121–134, doi:10.1016/S0012-365X(00)00463-5, MR 1874730 https://doi.org/10.1016%2FS0012-365X%2800%2900463-5 ↩

  12. This is a corrected version of Burr's conjecture from Wormald (1983). - Wormald, Nicholas C. (1983), "Subtrees of large tournaments", Combinatorial mathematics, X (Adelaide, 1982), Lecture Notes in Math., vol. 1036, Berlin: Springer, pp. 417–419, doi:10.1007/BFb0071535, ISBN 978-3-540-12708-6, MR 0731598 https://doi.org/10.1007%2FBFb0071535 ↩