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


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

Примеры

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

Однако в любом турнире с 2 n − 2 {displaystyle 2n-2} вершинами, средняя полустепень выхода равна n − 3 2 {displaystyle n-{frac {3}{2}}} , а максимальная полустепень выхода равно целому числу, большему или равному среднему значению. Таким образом, существует вершина с полустепенью выхода ⌈ n − 3 2 ⌉ = n − 1 {displaystyle leftlceil n-{frac {3}{2}} ight ceil =n-1} , которую можно использовать в качестве центральной вершины для копии P {displaystyle P} .

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

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

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

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

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

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

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



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru ©
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!