Гипотеза Самнера

Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для полидеревьев (ориентированных деревьев). Более точно, гипотеза Самнера (или гипотеза Самнера об универсальном турнире) утверждает, что любая ориентация любого дерева с вершинами является подграфом любого турнира с вершинами[1]. Гипотеза остаётся недоказанной. Кюн, Майкрофт и Остус[2] говорят о гипотезе как об «одной из наиболее известных задач о турнирах.»

Нерешённые проблемы математики: Любой ли турнир с вершинами содержит в качестве подграфа любое ориентированное дерево с вершинами?

Примеры

Пусть ориентированное дерево является звездой , в которой все рёбра ориентированы от центра к листьям. Тогда нельзя вложить в турнир, образованный из вершин регулярного -угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны , в то время как центральная вершина имеет большую полустепень выхода, .[3]. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев.

Однако в любом турнире с вершинами, средняя полустепень выхода равна , а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода , которую можно использовать в качестве центральной вершины для копии .

Частичные результаты

Известны следующие частичные результаты.

  • Гипотеза верна для всех достаточно больших значений [4].
  • Существует функция с асимптотической скоростью роста со свойством, что любое ориентированное дерево с вершинами может быть вложено в подграф любого турнира с вершинами. Кроме того, и более явно, .[5]
  • Существует функция , такая, что турниры с вершинами являются универсальными для ориентированных деревьев с листьями[6][7][8].
  • Существует функция , такая, что любое ориентированное дерево с вершинами с максимальной степенью, не превосходящей , образует подграф любого турнира с вершинами. Если является фиксированной константой, скорость асимптотического роста равна [2].
  • Любой «почти регулярный» турнир с вершинами содержит любое ориентированное дерево с вершинами[9].
  • Любая ориентированная гусеница с вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с вершинами[9].
  • Любой турнир с вершинами содержит в качестве подграфа любой ориентированный корневой граф с вершинами[10].

Связанные гипотезы

Розенфельд[11] высказал гипотезу, что любой ориентированный путь с вершинами (при ) может быть вложен в качестве подграфа в любой турнир с вершинами[9]. После частичных результатов, полученных Томасоном[12], гипотезу доказали Аве и Томасси[7].

Аве и Томасси[13], в свою очередь высказал усиленную гипотезу Самнера, что любой турнир с вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем листьями.

Бёрр[14] высказал гипотезу, что если граф требует и более цветов для раскраски графа , тогда любая ориентация графа содержит любую ориентацию дерева с вершинами. Поскольку полные графы требуют различные цвета для каждой вершины, гипотеза Самнера следует немедленно из гипотезу Бёрра[15]. Как показал Бёрр, ориентации графов, хроматическое число которых растёт квадратично от , являются универсальными для ориентированных деревьев.

Примечания

  1. (Kühn, Mycroft, Osthus 2011a). Наиболее ранняя опубликованная цитата, данная Даниэлой Кюн и др. принадлежит Райду и Вормолду ((Reid, Wormald 1983), (Wormald 1983)). Вормолд цитирует гипотезу как услышанную в частной беседе с Самнером.
  2. Kühn, Mycroft, Osthus, 2011a.
  3. Это пример взят из статьи Кюн, Майкрофта и Остуса ((Kühn, Mycroft, Osthus 2011a)).
  4. Kühn, Mycroft, Osthus, 2011b.
  5. Kühn, Mycroft, Osthus, 2011a; El Sahili, 2004. Более слабые и полученные ранее границы для функции можно найти в статьях Chung, 1981, Wormald, 1983, Häggkvist, Thomason, 1991, Havet, Thomassé, 2000b, Havet, 2002.
  6. Häggkvist, Thomason, 1991.
  7. Havet, Thomassé, 2000a.
  8. Havet, 2002.
  9. Reid, Wormald, 1983.
  10. Havet, Thomassé, 2000b.
  11. Rosenfeld, 1972.
  12. Thomason, 1986.
  13. В статье Аве ((Havet 2002)), но Аве приписывает его в этой статье Томасси.
  14. Burr, 1980.
  15. Это подправленная версия гипотезы Бёрра из статьи Вормолда ((Wormald 1983)).

Литература

  • Stefan A. Burr. Subtrees of directed graphs and hypergraphs // Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I. — 1980. — Т. 28. — С. 227—239. — (Congressus Numerantium).
  • Chung F.R.K. A note on subtrees in tournaments. Bell Laboratories, 1981. — (Internal Memorandum).. Как процитировано у Вормолда ((Wormald 1983)).
  • El Sahili A. Trees in tournaments // Journal of Combinatorial Theory. — 2004. Т. 92. С. 183—187. doi:10.1016/j.jctb.2004.04.002.
  • Roland Häggkvist, Andrew Thomason. Trees in tournaments // Combinatorica. — 1991. Т. 11. С. 123—130. doi:10.1007/BF01206356.
  • Frédéric Havet. Trees in tournaments // Discrete Mathematics. — 2002. Т. 243. С. 121—134. doi:10.1016/S0012-365X(00)00463-5.
  • Frédéric Havet, Stéphan Thomassé. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture // Journal of Combinatorial Theory. — 2000a. Т. 78. С. 243—273. doi:10.1006/jctb.1999.1945.
  • Frédéric Havet, Stéphan Thomassé. Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture // Journal of Graph Theory. — 2000b. Т. 35. С. 244—256. doi:10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H.
  • Daniela Kühn, Richard Mycroft, Deryk Osthus. An approximate version of Sumner's universal tournament conjecture // Journal of Combinatorial Theory. — 2011a. Т. 101. С. 415—447. doi:10.1016/j.jctb.2010.12.006.
  • Daniela Kühn, Richard Mycroft, Deryk Osthus. A proof of Sumner's universal tournament conjecture for large tournaments // Proceedings of the London Mathematical Society. — 2011b. Т. 102. С. 731—766. doi:10.1112/plms/pdq035. arXiv:1010.4430.
  • Embedding oriented n-trees in tournaments // Studia Scientiarum Mathematicarum Hungarica. — 1983. Т. 18. С. 377—387.
  • Rosenfeld M. Antidirected Hamiltonian paths in tournaments // Journal of Combinatorial Theory. — 1972. Т. 12. С. 93—99. doi:10.1016/0095-8956(72)90035-4.
  • Andrew Thomason. Paths and cycles in tournaments (англ.) // Transactions of the American Mathematical Society. — 1986. Vol. 296. P. 167—180. doi:10.2307/2000567.
  • Nicholas C. Wormald. Combinatorial mathematics, X (Adelaide, 1982). — Berlin: Springer, 1983. — Т. 1036. — С. 417—419. — (Lecture Notes in Math.). doi:10.1007/BFb0071535.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.