Меню Главная Случайная статья Настройки Гипотеза Самнера Материал из https://ru.wikipedia.org Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для полидеревьев[англ.] (ориентированных деревьев). Более точно, гипотеза Самнера (или гипотеза Самнера об универсальном турнире) утверждает, что любая ориентация любого дерева с ${\displaystyle n}$ вершинами является подграфом любого турнира с ${\displaystyle (2n-2)}$ вершинами[1]. Гипотеза остаётся недоказанной. Кюн, Майкрофт и Остус[2] говорят о гипотезе как об «одной из наиболее известных задач о турнирах.» Содержание 1 Примеры 2 Частичные результаты 3 Связанные гипотезы 4 Примечания 5 Литература 6 Ссылки Примеры Пусть ориентированное дерево ${\displaystyle P}$ является звездой ${\displaystyle K_{1,n-1}}$, в которой все рёбра ориентированы от центра к листьям. Тогда ${\displaystyle P}$ нельзя вложить в турнир, образованный из вершин регулярного ${\displaystyle (2n-3)}$-угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны ${\displaystyle n-2}$, в то время как центральная вершина ${\displaystyle P}$ имеет большую полустепень выхода, ${\displaystyle n-1}$.[3]. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев. Однако в любом турнире с ${\displaystyle 2n-2}$ вершинами, средняя полустепень выхода равна ${\displaystyle n-{\frac {3}{2}}}$, а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода ${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$, которую можно использовать в качестве центральной вершины для копии ${\displaystyle P}$. Частичные результаты Известны следующие частичные результаты. Гипотеза верна для всех достаточно больших значений ${\displaystyle n}$[4]. Существует функция ${\displaystyle f(n)}$ с асимптотической скоростью роста ${\displaystyle f(n)=2n+o(n)}$ со свойством, что любое ориентированное дерево с ${\displaystyle n}$ вершинами может быть вложено в подграф любого турнира с ${\displaystyle f(n)}$ вершинами. Кроме того, и более явно, ${\displaystyle f(n)\leq 3n-3}$.[5] Существует функция ${\displaystyle g(k)}$, такая, что турниры с ${\displaystyle n+g(k)}$ вершинами являются универсальными для ориентированных деревьев с ${\displaystyle k}$ листьями[6][7][8]. Существует функция ${\displaystyle h(n,\Delta )}$, такая, что любое ориентированное дерево с ${\displaystyle n}$ вершинами с максимальной степенью, не превосходящей ${\displaystyle \Delta }$, образует подграф любого турнира с ${\displaystyle h(n,\Delta )}$ вершинами. Если ${\displaystyle \Delta }$ является фиксированной константой, скорость асимптотического роста ${\displaystyle h(n,\Delta )}$ равна ${\displaystyle n+o(n)}$[2]. Любой «почти регулярный» турнир с ${\displaystyle 2n-2}$ вершинами содержит любое ориентированное дерево с ${\displaystyle n}$ вершинами[9]. Любая ориентированная гусеница с ${\displaystyle n}$ вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с ${\displaystyle (2n-2)}$ вершинами[9]. Любой турнир с ${\displaystyle (2n-2)}$ вершинами содержит в качестве подграфа любой ориентированный корневой граф[англ.] с ${\displaystyle n}$ вершинами[10]. Связанные гипотезы Розенфельд[11] высказал гипотезу, что любой ориентированный путь с ${\displaystyle n}$ вершинами (при ${\displaystyle n\geqslant 8}$) может быть вложен в качестве подграфа в любой турнир с ${\displaystyle n}$ вершинами[9]. После частичных результатов, полученных Томасоном[12], гипотезу доказали Аве и Томасси[7]. Аве и Томасси[13], в свою очередь высказал усиленную гипотезу Самнера, что любой турнир с ${\displaystyle n+k-1}$ вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем ${\displaystyle k}$ листьями. Бёрр[14] высказал гипотезу, что если граф ${\displaystyle G}$ требует ${\displaystyle 2n-2}$ и более цветов для раскраски графа ${\displaystyle G}$, тогда любая ориентация графа ${\displaystyle G}$ содержит любую ориентацию дерева с ${\displaystyle n}$ вершинами. Поскольку полные графы требуют различные цвета для каждой вершины, гипотеза Самнера следует немедленно из гипотезу Бёрра[15]. Как показал Бёрр, ориентации графов, хроматическое число которых растёт квадратично от ${\displaystyle n}$, являются универсальными для ориентированных деревьев. Примечания (Khn, Mycroft, Osthus 2011a). Наиболее ранняя опубликованная цитата, данная Даниэлой Кюн и др. принадлежит Райду и Вормолду ((Reid, Wormald 1983), (Wormald 1983)). Вормолд цитирует гипотезу как услышанную в частной беседе с Самнером. 1 2 Khn, Mycroft, Osthus, 2011a. Это пример взят из статьи Кюн, Майкрофта и Остуса ((Khn, Mycroft, Osthus 2011a)). Khn, Mycroft, Osthus, 2011b. Khn, Mycroft, Osthus, 2011a; El Sahili, 2004. Более слабые и полученные ранее границы для функции ${\displaystyle f(n)}$ можно найти в статьях Chung, 1981, Wormald, 1983, Hggkvist, Thomason, 1991, Havet, Thomass, 2000b, Havet, 2002. Hggkvist, Thomason, 1991. 1 2 Havet, Thomass, 2000a. Havet, 2002. 1 2 3 Reid, Wormald, 1983. Havet, Thomass, 2000b. Rosenfeld, 1972. Thomason, 1986. В статье Аве ((Havet 2002)), но Аве приписывает его в этой статье Томасси. Burr, 1980. Это подправленная версия гипотезы Бёрра из статьи Вормолда ((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). El Sahili A. Trees in tournaments // Journal of Combinatorial Theory. — 2004. — Т. 92. — С. 183—187. — doi:10.1016/j.jctb.2004.04.002. Roland Hggkvist, Andrew Thomason. Trees in tournaments // Combinatorica. — 1991. — Т. 11. — С. 123—130. — doi:10.1007/BF01206356. Frdric Havet. Trees in tournaments // Discrete Mathematics. — 2002. — Т. 243. — С. 121—134. — doi:10.1016/S0012-365X(00)00463-5. Frdric Havet, Stphan 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. Frdric Havet, Stphan 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 Khn, 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 Khn, 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. Ссылки Sumner’s Universal Tournament Conjecture (1971) Архивная копия от 27 февраля 2014 на Wayback Machine, D. B. West, updated July 2008.