Гипотеза Самнера
Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для полидеревьев (ориентированных деревьев). Более точно, гипотеза Самнера (или гипотеза Самнера об универсальном турнире) утверждает, что любая ориентация любого дерева с [math]\displaystyle{ n }[/math] вершинами является подграфом любого турнира с [math]\displaystyle{ (2n-2) }[/math] вершинами[1]. Гипотеза остаётся недоказанной. Кюн, Майкрофт и Остус[2] говорят о гипотезе как об «одной из наиболее известных задач о турнирах.»
Примеры
Пусть ориентированное дерево [math]\displaystyle{ P }[/math] является звездой [math]\displaystyle{ K_{1,n-1} }[/math], в которой все рёбра ориентированы от центра к листьям. Тогда [math]\displaystyle{ P }[/math] нельзя вложить в турнир, образованный из вершин регулярного [math]\displaystyle{ (2n-3) }[/math]-угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны [math]\displaystyle{ n-2 }[/math], в то время как центральная вершина [math]\displaystyle{ P }[/math] имеет большую полустепень выхода, [math]\displaystyle{ n-1 }[/math].[3]. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев.
Однако в любом турнире с [math]\displaystyle{ 2n-2 }[/math] вершинами, средняя полустепень выхода равна [math]\displaystyle{ n-\frac{3}{2} }[/math], а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода [math]\displaystyle{ \left\lceil n-\frac{3}{2}\right\rceil=n-1 }[/math], которую можно использовать в качестве центральной вершины для копии [math]\displaystyle{ P }[/math].
Частичные результаты
Известны следующие частичные результаты.
- Гипотеза верна для всех достаточно больших значений [math]\displaystyle{ n }[/math][4].
- Существует функция [math]\displaystyle{ f(n) }[/math] с асимптотической скоростью роста [math]\displaystyle{ f(n)=2n+o(n) }[/math] со свойством, что любое ориентированное дерево с [math]\displaystyle{ n }[/math] вершинами может быть вложено в подграф любого турнира с [math]\displaystyle{ f(n) }[/math] вершинами. Кроме того, и более явно, [math]\displaystyle{ f(n)\le 3n-3 }[/math].[5]
- Существует функция [math]\displaystyle{ g(k) }[/math], такая, что турниры с [math]\displaystyle{ n+g(k) }[/math] вершинами являются универсальными для ориентированных деревьев с [math]\displaystyle{ k }[/math] листьями[6][7][8].
- Существует функция [math]\displaystyle{ h(n,\Delta) }[/math], такая, что любое ориентированное дерево с [math]\displaystyle{ n }[/math] вершинами с максимальной степенью, не превосходящей [math]\displaystyle{ \Delta }[/math], образует подграф любого турнира с [math]\displaystyle{ h(n,\Delta) }[/math] вершинами. Если [math]\displaystyle{ \Delta }[/math] является фиксированной константой, скорость асимптотического роста [math]\displaystyle{ h(n,\Delta) }[/math] равна [math]\displaystyle{ n+o(n) }[/math][2].
- Любой «почти регулярный» турнир с [math]\displaystyle{ 2n-2 }[/math] вершинами содержит любое ориентированное дерево с [math]\displaystyle{ n }[/math] вершинами[9].
- Любая ориентированная гусеница с [math]\displaystyle{ n }[/math] вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с [math]\displaystyle{ (2n-2) }[/math] вершинами[9].
- Любой турнир с [math]\displaystyle{ (2n-2) }[/math] вершинами содержит в качестве подграфа любой ориентированный корневой граф с [math]\displaystyle{ n }[/math] вершинами[10].
Связанные гипотезы
Розенфельд[11] высказал гипотезу, что любой ориентированный путь с [math]\displaystyle{ n }[/math] вершинами (при [math]\displaystyle{ n\geqslant 8 }[/math]) может быть вложен в качестве подграфа в любой турнир с [math]\displaystyle{ n }[/math] вершинами[9]. После частичных результатов, полученных Томасоном[12], гипотезу доказали Аве и Томасси[7].
Аве и Томасси[13], в свою очередь высказал усиленную гипотезу Самнера, что любой турнир с [math]\displaystyle{ n+k-1 }[/math] вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем [math]\displaystyle{ k }[/math] листьями.
Бёрр[14] высказал гипотезу, что если граф [math]\displaystyle{ G }[/math] требует [math]\displaystyle{ 2n-2 }[/math] и более цветов для раскраски графа [math]\displaystyle{ G }[/math], тогда любая ориентация графа [math]\displaystyle{ G }[/math] содержит любую ориентацию дерева с [math]\displaystyle{ n }[/math] вершинами. Поскольку полные графы требуют различные цвета для каждой вершины, гипотеза Самнера следует немедленно из гипотезу Бёрра[15]. Как показал Бёрр, ориентации графов, хроматическое число которых растёт квадратично от [math]\displaystyle{ n }[/math], являются универсальными для ориентированных деревьев.
Примечания
- ↑ (Kühn, Mycroft, Osthus 2011a). Наиболее ранняя опубликованная цитата, данная Даниэлой Кюн и др. принадлежит Райду и Вормолду ((Reid, Wormald 1983), (Wormald 1983)). Вормолд цитирует гипотезу как услышанную в частной беседе с Самнером.
- ↑ 2,0 2,1 Kühn, Mycroft, Osthus, 2011a.
- ↑ Это пример взят из статьи Кюн, Майкрофта и Остуса ((Kühn, Mycroft, Osthus 2011a)).
- ↑ Kühn, Mycroft, Osthus, 2011b.
- ↑ Kühn, Mycroft, Osthus, 2011a; El Sahili, 2004. Более слабые и полученные ранее границы для функции [math]\displaystyle{ f(n) }[/math] можно найти в статьях Chung, 1981, Wormald, 1983, Häggkvist, Thomason, 1991, Havet, Thomassé, 2000b, Havet, 2002.
- ↑ Häggkvist, Thomason, 1991.
- ↑ 7,0 7,1 Havet, Thomassé, 2000a.
- ↑ Havet, 2002.
- ↑ 9,0 9,1 9,2 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).
- 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.
Ссылки
- Sumner’s Universal Tournament Conjecture (1971) Архивная копия от 27 февраля 2014 на Wayback Machine, D. B. West, updated July 2008.
Для улучшения этой статьи желательно: |