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

Каждый ли -вершинный турнир содержит в качестве подграфа каждое -вершинно-ориентированное дерево?${\ Displaystyle (2n-2)}$${\ Displaystyle п}$

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

Пусть полидерево — звезда , у которой все ребра ориентированы наружу от центральной вершины к листьям. Тогда нельзя вложить в турнир, образованный из вершин правильного -угольника, направив каждое ребро вокруг многоугольника по часовой стрелке. Ибо в этом турнире каждая вершина имеет степень входа и выхода, равные , а центральная вершина имеет большую степень выхода . ^[3] Таким образом, если гипотеза Самнера верна, она даст наилучший возможный размер универсального графа для полидеревьев.${\ Displaystyle Р}$ ${\ Displaystyle К_ {1, п-1}}$${\ Displaystyle Р}$${\displaystyle 2n-3}$${\displaystyle n-2}$${\displaystyle P}$${\displaystyle n-1}$

Однако в каждом турнире вершин средняя степень исхода равна , а максимальная степень исхода — это целое число, большее или равное среднему значению. Следовательно, существует вершина исходящей степени , которую можно использовать как центральную вершину для копии .${\displaystyle 2n-2}$${\displaystyle n-{\frac {3}{2}}}$${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$${\displaystyle P}$

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

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

6-вершинный турнир и копии каждого 4-вершинного ориентированного дерева в нем.