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

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

Примеры

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга. Как процитировано у Вормолда (Шаблон:Harv).
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

Ссылки

• Sumner’s Universal Tournament Conjecture (1971) Шаблон:Wayback, D. B. West, updated July 2008.