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

Пусть ориентированное дерево ${\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), D. B. West, updated July 2008.