WikiSort.ru - Не сортированное

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

Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для полидеревьев^[en] (ориентированных деревьев). Более точно, гипотеза Самнера (или гипотеза Самнера об универсальном турнире) утверждает, что любая ориентация^?! любого дерева с ${\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)}$ вершинами содержит в качестве подграфа любой ориентированный корневой граф^[en] с ${\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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.