Русская Википедия:Гипотеза Самнера
Шаблон:Unsolved Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 1971 высказал гипотезу, что турниры являются универсальными графами для Шаблон:Не переведено 5 (ориентированных деревьев). Более точно, гипотеза Самнера (или гипотеза Самнера об универсальном турнире) утверждает, что любая ориентация любого дерева с <math>n</math> вершинами является подграфом любого турнира с <math>(2n-2)</math> вершинами[1]. Гипотеза остаётся недоказанной. Кюн, Майкрофт и ОстусШаблон:Sfn говорят о гипотезе как об «одной из наиболее известных задач о турнирах.»
Примеры
Пусть ориентированное дерево <math>P</math> является звездой <math>K_{1,n-1}</math>, в которой все рёбра ориентированы от центра к листьям. Тогда <math>P</math> нельзя вложить в турнир, образованный из вершин регулярного <math>(2n-3)</math>-угольника путём направления всех рёбер по часовой стрелке вокруг многоугольника. Для этого турнира любая полустепень входа и любая полустепень выхода равны <math>n-2</math>, в то время как центральная вершина <math>P</math> имеет большую полустепень выхода, <math>n-1</math>.[2]. Таким образом, если гипотеза Самнера верна, она даёт наилучший возможный размер универсального графа для ориентированных деревьев.
Однако в любом турнире с <math>2n-2</math> вершинами, средняя полустепень выхода равна <math>n-\frac{3}{2}</math>, а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода <math>\left\lceil n-\frac{3}{2}\right\rceil=n-1</math>, которую можно использовать в качестве центральной вершины для копии <math>P</math>.
Частичные результаты
Известны следующие частичные результаты.
- Гипотеза верна для всех достаточно больших значений <math>n</math>Шаблон:Sfn.
- Существует функция <math>f(n)</math> с асимптотической скоростью роста <math>f(n)=2n+o(n)</math> со свойством, что любое ориентированное дерево с <math>n</math> вершинами может быть вложено в подграф любого турнира с <math>f(n)</math> вершинами. Кроме того, и более явно, <math>f(n)\le 3n-3</math>.[3]
- Существует функция <math>g(k)</math>, такая, что турниры с <math>n+g(k)</math> вершинами являются универсальными для ориентированных деревьев с <math>k</math> листьямиШаблон:SfnШаблон:SfnШаблон:Sfn.
- Существует функция <math>h(n,\Delta)</math>, такая, что любое ориентированное дерево с <math>n</math> вершинами с максимальной степенью, не превосходящей <math>\Delta</math>, образует подграф любого турнира с <math>h(n,\Delta)</math> вершинами. Если <math>\Delta</math> является фиксированной константой, скорость асимптотического роста <math>h(n,\Delta)</math> равна <math>n+o(n)</math>Шаблон:Sfn.
- Любой «почти регулярный» турнир с <math>2n-2</math> вершинами содержит любое ориентированное дерево с <math>n</math> вершинамиШаблон:Sfn.
- Любая ориентированная гусеница с <math>n</math> вершинами и диаметром, не превосходящим четырёх, может быть вложена в качестве подграфа в любой турнир с <math>(2n-2)</math> вершинамиШаблон:Sfn.
- Любой турнир с <math>(2n-2)</math> вершинами содержит в качестве подграфа любой Шаблон:Не переведено 5 с <math>n</math> вершинамиШаблон:Sfn.
Связанные гипотезы
РозенфельдШаблон:Sfn высказал гипотезу, что любой ориентированный путь с <math>n</math> вершинами (при <math>n\geqslant 8</math>) может быть вложен в качестве подграфа в любой турнир с <math>n</math> вершинамиШаблон:Sfn. После частичных результатов, полученных ТомасономШаблон:Sfn, гипотезу доказали Аве и ТомассиШаблон:Sfn.
Аве и Томасси[4], в свою очередь высказал усиленную гипотезу Самнера, что любой турнир с <math>n+k-1</math> вершинами содержит в качестве подграфа любое ориентированное дерево с не более чем <math>k</math> листьями.
БёррШаблон:Sfn высказал гипотезу, что если граф <math>G</math> требует <math>2n-2</math> и более цветов для раскраски графа <math>G</math>, тогда любая ориентация графа <math>G</math> содержит любую ориентацию дерева с <math>n</math> вершинами. Поскольку полные графы требуют различные цвета для каждой вершины, гипотеза Самнера следует немедленно из гипотезу Бёрра[5]. Как показал Бёрр, ориентации графов, хроматическое число которых растёт квадратично от <math>n</math>, являются универсальными для ориентированных деревьев.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга. Как процитировано у Вормолда (Шаблон:Harv).
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
Ссылки
- Sumner’s Universal Tournament Conjecture (1971) Шаблон:Wayback, D. B. West, updated July 2008.
- ↑ Шаблон:Harv. Наиболее ранняя опубликованная цитата, данная Даниэлой Кюн и др. принадлежит Райду и Вормолду (Шаблон:Harv, Шаблон:Harv). Вормолд цитирует гипотезу как услышанную в частной беседе с Самнером.
- ↑ Это пример взят из статьи Кюн, Майкрофта и Остуса (Шаблон:Harv).
- ↑ Шаблон:Harvnb; Шаблон:Harvnb. Более слабые и полученные ранее границы для функции <math>f(n)</math> можно найти в статьях Шаблон:Harvnb, Шаблон:Harvnb, Шаблон:Harvnb, Шаблон:Harvnb, Шаблон:Harvnb.
- ↑ В статье Аве (Шаблон:Harv), но Аве приписывает его в этой статье Томасси.
- ↑ Это подправленная версия гипотезы Бёрра из статьи Вормолда (Шаблон:Harv).
