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

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

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

Примеры

Пусть ориентированное дерево $P$ является звездой $K_{1,n-1}$, в которой все рёбра ориентированы от центра к листьям. Тогда $P$ нельзя вложить в турнир, образованный из вершин регулярного $(2n-3)$-угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны $n-2$, в то время как центральная вершина $P$ имеет большую полустепень выхода, $n-1$.. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев.

Однако в любом турнире с $2n-2$ вершинами, средняя полустепень выхода равна $n-{\frac {3}{2}}$, а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода $\left\lceil n-{\frac {3}{2}}\right\rceil =n-1$, которую можно использовать в качестве центральной вершины для копии $P$.

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

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

• Гипотеза верна для всех достаточно больших значений $n$.
• Существует функция $f(n)$ с асимптотической скоростью роста $f(n)=2n+o(n)$ со свойством, что любое ориентированное дерево с $n$ вершинами может быть вложено в подграф любого турнира с $f(n)$ вершинами. Кроме того, и более явно, $f(n)\leq 3n-3$.
• Существует функция $g(k)$, такая, что турниры с $n+g(k)$ вершинами являются универсальными для ориентированных деревьев с $k$ листьями.
• Существует функция $h(n,\Delta )$, такая, что любое ориентированное дерево с $n$ вершинами с максимальной степенью, не превосходящей $\Delta$, образует подграф любого турнира с $h(n,\Delta )$ вершинами. Если $\Delta$ является фиксированной константой, скорость асимптотического роста $h(n,\Delta )$ равна $n+o(n)$.
• Любой «почти регулярный» турнир с $2n-2$ вершинами содержит любое ориентированное дерево с $n$ вершинами.
• Любая ориентированная гусеница с $n$ вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с $(2n-2)$ вершинами.
• Любой турнир с $(2n-2)$ вершинами содержит в качестве подграфа любой ориентированный корневой граф с $n$ вершинами.

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

Розенфельд высказал гипотезу, что любой ориентированный путь с $n$ вершинами (при $n\geqslant 8$) может быть вложен в качестве подграфа в любой турнир с $n$ вершинами. После частичных результатов, полученных Томасоном, гипотезу доказали Аве и Томасси.

Аве и Томасси, в свою очередь высказал усиленную гипотезу Самнера, что любой турнир с $n+k-1$ вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем $k$ листьями.

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

Ссылки

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