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

Примеры Пусть ориентированное дерево является звездой , в которой все рёбра ориентированы от центра к листьям. Тогда нельзя вложить в турнир, образованный из вершин регулярного -угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны , в то время как центральная вершина имеет большую полустепень выхода, .Это пример взят из статьи Кюн, Майкрофта и Остуса ().. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев.

Однако в любом турнире с вершинами, средняя полустепень выхода равна , а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода , которую можно использовать в качестве центральной вершины для копии .

Частичные результаты Известны следующие частичные результаты: Гипотеза верна для всех достаточно больших значений . Существует функция с асимптотической скоростью роста со свойством, что любое ориентированное дерево с вершинами может быть вложено в подграф любого турнира с вершинами. Кроме того, и более явно, .; . Более слабые и полученные ранее границы для функции можно найти в статьях , , , , . Существует функция , такая, что турниры с вершинами являются универсальными для ориентированных деревьев с листьями. Существует функция , такая, что любое ориентированное дерево с вершинами с максимальной степенью, не превосходящей , образует подграф любого турнира с вершинами. Если является фиксированной константой, скорость асимптотического роста равна . Любой «почти регулярный» турнир с вершинами содержит любое ориентированное дерево с вершинами. Любая ориентированная гусеница с вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с вершинами. Любой турнир с вершинами содержит в качестве подграфа любой с вершинами.

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

Аве и ТомассиВ статье Аве (), но Аве приписывает его в этой статье Томасси., в свою очередь, высказали усиленную гипотезу Самнера, что любой турнир с вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем листьями.

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

Примечания

Литература

. Как процитировано у Вормолда ().

Ссылки Sumner’s Universal Tournament Conjecture (1971) , D. B. West, updated July 2008.

Категория:Теория графов Категория:Математические гипотезы