WikiDer > Гипотеза Самнерса - Википедия
Нерешенная проблема в математике: Каждый -vertex турнир содержит в качестве подграфа каждый -вершинно ориентированное дерево? (больше нерешенных задач по математике) |
Гипотеза Самнера (также называемый Гипотеза о универсальном турнире Самнера) утверждает, что каждый ориентация каждого -вертекс дерево это подграф каждого -вертекс турнир.[1] Дэвид Самнер, а теоретик графов на Университет Южной Каролины, предполагаемый в 1971 г. турниры находятся универсальные графики за многодеревья. Гипотеза была доказана для всех больших к Даниэла Кюн, Ричард Майкрофт и Дерик Остхус.[2]
Примеры
Пусть polytree быть звезда , в котором все ребра ориентированы наружу от центральной вершины к листам. Потом, не может быть вложен в турнир, образованный из вершин регулярного -gon, направляя каждое ребро вокруг многоугольника по часовой стрелке. Ведь в этом турнире каждая вершина имеет степень и исход, равные , а центральная вершина в имеет большую исходящую степень .[3] Таким образом, если она верна, гипотеза Самнера дала бы наилучший возможный размер универсального графа для многодеревьев.
Однако в каждом турнире вершин, средняя исходящая степень равна , а максимальная исходящая степень - это целое число, большее или равное среднему. Следовательно, существует вершина исходящей степени , которая может использоваться как центральная вершина для копии .
Частичные результаты
Были доказаны следующие частичные результаты гипотезы.
- Есть функция с асимптотической скоростью роста с тем свойством, что каждый -вершинного многодерева можно вложить как подграф любого -вертекс турнир. Дополнительно и более подробно, .[4]
- Есть функция такие, что турниры на вершины универсальны для многодеревьев с листья.[5]
- Есть функция так что каждый -вершинное многодерево с максимальной степенью не выше формирует подграф каждого турнира с вершины. Когда - фиксированная константа, асимптотическая скорость роста является .[6]
- Каждый «почти регулярный» турнир на вершин содержит каждый -вершинное многодерево.[7]
- Каждая ориентация -вертекс гусеница с диаметр не более четырех могут быть вложены как подграф каждого -вертекс турнир.[7]
- Каждый -vertex турнир содержит в качестве подграфа каждый -вертекс древообразование.[8]
Связанные предположения
Розенфельд (1972) предположил, что любая ориентация -вертекс граф путей (с ) можно вложить как подграф в любой -вертекс турнир.[7] После частичных результатов Томасон (1986), это было доказано Хаве и Томассе (2000a).
Хаве и Томассе[9] в свою очередь предположил усиление гипотезы Самнера, что каждый турнир вершины содержат в качестве подграфа каждое многодерево с не более чем листья. Это было подтверждено почти для каждого дерева Майкрофтом и Найя (2018).
Берр (1980) предположил, что всякий раз, когда граф требует или больше цветов в раскраска из , то каждая ориентация содержит каждую ориентацию -вершинное дерево. Поскольку полные графы требуют разного цвета для каждой вершины, гипотеза Самнера немедленно вытекала бы из гипотезы Берра.[10] Как показал Барр, ориентации графов, хроматическое число которых растет квадратично в зависимости от универсальны для многодеревьев.
Примечания
- ^ Кюн, Майкрофт и Остхус (2011a). Однако самые ранние опубликованные цитаты, приведенные Kühn et al. должны Рид и Вормальд (1983) и Вормальд (1983). Вормальд (1983) цитирует эту гипотезу как недатированное частное сообщение Самнера.
- ^ Кюн, Майкрофт и Остхус (2011b).
- ^ Этот пример взят из Кюн, Майкрофт и Остхус (2011a).
- ^ Кюн, Майкрофт и Остхус (2011a) и Эль Сахили (2004). Для более ранних более слабых оценок на , видеть Чанг (1981), Вормальд (1983), Хэггквист и Томасон (1991), Хаве и Томассе (2000b), и Хавет (2002).
- ^ Хэггквист и Томасон (1991); Хаве и Томассе (2000a); Хавет (2002).
- ^ Кюн, Майкрофт и Остхус (2011a).
- ^ а б c Рид и Вормальд (1983).
- ^ Хаве и Томассе (2000b).
- ^ В Хавет (2002), но совместно зачисленные Томассе в этой статье.
- ^ Это исправленная версия гипотезы Берра из Вормальд (1983).
Рекомендации
- Берр, Стефан А. (1980), «Поддеревья ориентированных графов и гиперграфов», Труды одиннадцатой Юго-Восточной конференции по комбинаторике, теории графов и вычислениям (Флоридский Атлантический университет, Бока-Ратон, Флорида, 1980), Vol. я, Congressus Numerantium, 28, стр. 227–239, МИСТЕР 0608430.
- Чанг, F.R.K. (1981), Примечание о поддеревьях в турнирах, Внутренний меморандум, Bell Laboratories. Как цитирует Вормальд (1983).
- Эль Сахили, А. (2004), «Деревья на турнирах», Журнал комбинаторной теории, Серия B, 92 (1): 183–187, Дои:10.1016 / j.jctb.2004.04.002, МИСТЕР 2078502.
- Хэггквист, Роланд; Томасон, Эндрю (1991), «Деревья в турнирах», Комбинаторика, 11 (2): 123–130, Дои:10.1007 / BF01206356, МИСТЕР 1136161.
- Хаве, Фредерик (2002), «Деревья на турнирах», Дискретная математика, 243 (1–3): 121–134, Дои:10.1016 / S0012-365X (00) 00463-5, МИСТЕР 1874730.
- Хаве, Фредерик; Томассе, Стефан (2000a), "Ориентированные гамильтоновы пути в турнирах: доказательство гипотезы Розенфельда", Журнал комбинаторной теории, Серия B, 78 (2): 243–273, Дои:10.1006 / jctb.1999.1945, МИСТЕР 1750898.
- Хаве, Фредерик; Томассе, Стефан (2000b), «Медианные порядки турниров: инструмент для решения второй проблемы соседства и гипотезы Самнера», Журнал теории графов, 35 (4): 244–256, Дои:10.1002 / 1097-0118 (200012) 35: 4 <244 :: AID-JGT2> 3.0.CO; 2-H, МИСТЕР 1791347.
- Кюн, Даниела; Майкрофт, Ричард; Остхус, Дерик (2011a), «Приблизительная версия универсальной гипотезы Самнера о турнире», Журнал комбинаторной теории, Серия B, 101 (6): 415–447, arXiv:1010.4429, Дои:10.1016 / j.jctb.2010.12.006, МИСТЕР 2832810, Zbl 1234.05115.
- Кюн, Даниела; Майкрофт, Ричард; Остхус, Дерик (2011b), «Доказательство универсальной турнирной гипотезы Самнера для крупных турниров», Труды Лондонского математического общества, Третья серия, 102 (4): 731–766, arXiv:1010.4430, Дои:10.1112 / plms / pdq035, МИСТЕР 2793448, Zbl 1218.05034.
- Найя, Тассио (2018), Большие структуры в плотных ориентированных графах, Докторская диссертация, Бирмингемский университет.
- Reid, K. B .; Wormald, N. C. (1983), "Вложение ориентировано п-деревья в турнирах », Studia Scientiarum Mathematicarum Hungarica, 18 (2–4): 377–387, МИСТЕР 0787942.
- Розенфельд, М. (1972), "Антинаправленные гамильтоновы пути в турнирах", Журнал комбинаторной теории, Серия B, 12: 93–99, Дои:10.1016/0095-8956(72)90035-4, МИСТЕР 0285452.
- Томасон, Эндрю (1986), «Пути и циклы в турнирах», Труды Американского математического общества, 296 (1): 167–180, Дои:10.2307/2000567, МИСТЕР 0837805.
- Вормальд, Николас К. (1983), «Поддеревья больших турниров», Комбинаторная математика, X (Аделаида, 1982), Конспект лекций по математике, 1036, Берлин: Springer, стр. 417–419, Дои:10.1007 / BFb0071535, МИСТЕР 0731598.
внешняя ссылка
- Гипотеза Универсального Турнира Самнера (1971), Д. Б. Уэст, обновлено в июле 2008 г.