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

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

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

Примеры

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