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

Нерешённые проблемы математики: Любой ли турнир с ${\displaystyle (2n-2)}$ вершинами содержит в качестве подграфа любое ориентированное дерево с ${\displaystyle n}$ вершинами?

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

Пусть ориентированное дерево ${\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}$, являются универсальными для ориентированных деревьев.

• Sumner’s Universal Tournament Conjecture (1971) Архивная копия от 27 февраля 2014 на Wayback Machine, D. B. West, updated July 2008.

У этой статьи есть несколько проблем, помогите их исправить: Необходимо проверить качество перевода c неуказанного языка, исправить содержательные и стилистические ошибки. Вы можете помочь улучшить эту статью (см. также рекомендации по переводу). Оригинал не указан. Пожалуйста, укажите его. (16 апреля 2018) Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (16 апреля 2018) Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.