Гипотеза Самнерса - Sumners conjecture - Wikipedia

Нерешенная проблема в математике:

Каждый

{ displaystyle (2n-2)}

-vertex турнир содержит в качестве подграфа каждый

{ displaystyle n}

-вершинно ориентированное дерево?

(больше нерешенных задач по математике)

Турнир с 6 вершинами и копии каждого дерева с 4 вершинами в нем.

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

Примеры

Пусть polytree ${ displaystyle P}$ быть звезда ${ displaystyle K_ {1, n-1}}$ , в котором все ребра ориентированы наружу от центральной вершины к листам. Потом, ${ displaystyle P}$ не может быть вложен в турнир, образованный из вершин регулярного ${ displaystyle 2n-3}$ -gon, направляя каждое ребро вокруг многоугольника по часовой стрелке. Ведь в этом турнире каждая вершина имеет степень и исход, равные ${ 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 f (п)}$ с асимптотической скоростью роста ${ Displaystyle е (п) = 2n + о (п)}$ с тем свойством, что каждый ${ displaystyle n}$ -вершинного многодерева можно вложить как подграф любого ${ Displaystyle f (п)}$ -вертекс турнир. Дополнительно и более подробно, ${ Displaystyle е (п) leq 3n-3}$ .^[4]
Есть функция ${ displaystyle g (k)}$ такие, что турниры на ${ Displaystyle п + г (к)}$ вершины универсальны для многодеревьев с ${ displaystyle k}$ листья.^[5]
Есть функция ${ Displaystyle ч (п, Delta)}$ так что каждый ${ displaystyle n}$ -вершинное многодерево с максимальной степенью не выше ${ displaystyle Delta}$ формирует подграф каждого турнира с ${ Displaystyle ч (п, Delta)}$ вершины. Когда ${ displaystyle Delta}$ - фиксированная константа, асимптотическая скорость роста ${ Displaystyle ч (п, Delta)}$ является ${ Displaystyle п + о (п)}$ .^[6]
Каждый «почти регулярный» турнир на ${ displaystyle 2n-2}$ вершин содержит каждый ${ displaystyle n}$ -вершинное многодерево.^[7]
Каждая ориентация ${ displaystyle n}$ -вертекс гусеница с диаметр не более четырех могут быть вложены как подграф каждого ${ displaystyle (2n-2)}$ -вертекс турнир.^[7]
Каждый ${ displaystyle (2n-2)}$ -vertex турнир содержит в качестве подграфа каждый ${ displaystyle n}$ -вертекс древообразование.^[8]

Связанные предположения

Розенфельд (1972) предположил, что любая ориентация ${ displaystyle n}$ -вертекс граф путей (с ${ displaystyle n geq 8}$ ) можно вложить как подграф в любой ${ displaystyle n}$ -вертекс турнир.^[7] После частичных результатов Томасон (1986), это было доказано Хаве и Томассе (2000a).

Хаве и Томассе^[9] в свою очередь предположил усиление гипотезы Самнера, что каждый турнир ${ Displaystyle п + к-1}$ вершины содержат в качестве подграфа каждое многодерево с не более чем ${ displaystyle k}$ листья. Это было подтверждено почти для каждого дерева Майкрофтом и Найя (2018).

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

Примечания

^ Кюн, Майкрофт и Остхус (2011a). Однако самые ранние опубликованные цитаты, приведенные Kühn et al. должны Рид и Вормальд (1983) и Вормальд (1983). Вормальд (1983) цитирует эту гипотезу как недатированное частное сообщение Самнера.
^ Кюн, Майкрофт и Остхус (2011b).
^ Этот пример взят из Кюн, Майкрофт и Остхус (2011a).
^ Кюн, Майкрофт и Остхус (2011a) и Эль Сахили (2004). Для более ранних более слабых оценок на ${ Displaystyle f (п)}$ , видеть Чанг (1981), Вормальд (1983), Хэггквист и Томасон (1991), Хаве и Томассе (2000b), и Хавет (2002).
^ Хэггквист и Томасон (1991); Хаве и Томассе (2000a); Хавет (2002).
^ Кюн, Майкрофт и Остхус (2011a).
^ ^а ^б ^c Рид и Вормальд (1983).
^ Хаве и Томассе (2000b).
^ В Хавет (2002), но совместно зачисленные Томассе в этой статье.
^ Это исправленная версия гипотезы Берра из Вормальд (1983).

внешняя ссылка

Гипотеза Универсального Турнира Самнера (1971), Д. Б. Уэст, обновлено в июле 2008 г.

[1] Кюн, Майкрофт и Остхус (2011a). Однако самые ранние опубликованные цитаты, приведенные Kühn et al. должны Рид и Вормальд (1983) и Вормальд (1983). Вормальд (1983) цитирует эту гипотезу как недатированное частное сообщение Самнера.

[2] Кюн, Майкрофт и Остхус (2011b).

[3] Этот пример взят из Кюн, Майкрофт и Остхус (2011a).

[4] Кюн, Майкрофт и Остхус (2011a) и Эль Сахили (2004). Для более ранних более слабых оценок на ${ Displaystyle f (п)}$ , видеть Чанг (1981), Вормальд (1983), Хэггквист и Томасон (1991), Хаве и Томассе (2000b), и Хавет (2002).

[5] Хэггквист и Томасон (1991); Хаве и Томассе (2000a); Хавет (2002).

[6] Кюн, Майкрофт и Остхус (2011a).

[rw83-7] а ^б ^c Рид и Вормальд (1983).

[8] Хаве и Томассе (2000b).

[9] В Хавет (2002), но совместно зачисленные Томассе в этой статье.

[10] Это исправленная версия гипотезы Берра из Вормальд (1983).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]