Дэвид Самнер (специалист в теории графов из университета Южной Каролины) в 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} вершинами (при 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} , являются универсальными для ориентированных деревьев.