Девід Самнер (фахівець у теорії графів із університету Південної Кароліни) 1971 року висловив гіпотезу, що турніри є універсальними графами задля (орієнтованих дерев). Точніше, гіпо́теза Са́мнера (або гіпо́теза Са́мнера про універса́льний турні́р) стверджує, що будь-яка орієнтація будь-якого дерева з вершинами є підграфом будь-якого турніру з вершинами. Найраніша опублікована цитата, яку навела Даніела Кюн та ін. надлежить Райду і Вормолду (, ). Вормолд цитує гіпотезу як почуту в приватній бесіді зі Самнером.. Гіпотеза залишається недоведеною. Кюн, Майкрофт і Остус називають гіпотезу «однією з найвідоміших задач про турніри».
Приклади Нехай орієнтоване дерево є зіркою , в якій усі ребра орієнтовані від центра до листків. Тоді не можна вкласти в турнір, утворений із вершин регулярного -кутника шляхом спрямування всіх ребер за годинниковою стрілкою навколо многокутника. Для цього турніру будь-який напівстепінь входу і будь-який напівстепень виходу дорівнюють , тоді як центральна вершина має більший напівстепінь виходу, Цей приклад взято зі статті Кюн, Майкрофта і Остуса ().. Таким чином, якщо гіпотеза Самнера істинна, вона дає найкращий можливий розмір універсального графа для орієнтованих дерев.
Однак у будь-якому турнірі з вершинами, середній напівстепінь виходу дорівнює , а найбільший напівстепінь виходу дорівнює цілому числу, більшому або рівному середньому значенню. Таким чином, існує вершина з напівстепенем виходу , яку можна використати як центральну вершину для копії .
Часткові результати Відомі такі часткові результати.
Гіпотеза істинна для всіх досить великих значень . Існує функція з асимптотичною швидкістю зростання зі властивістю, що будь-яке орієнтоване дерево з вершинами можна вкласти в підграф будь-якого турніру з вершин. Крім того, і більш явно, .; . Более слабые и полученные ранее границы для функции можно найти в статьях , , , , . Існує функція , така, що турніри з вершинами є універсальними для орієнтованих дерев з листками. Існує функція , така, що будь-яке орієнтоване дерево з вершинами з найбільшим степенем, що не перевищує , утворює підграф будь-якого турніру з вершинами. Якщо є фіксованою константою, швидкість асимптотичного зростання дорівнює . Будь-який «майже регулярний» турнір із вершинами містить будь-яке орієнтоване дерево з вершин. Будь-яку орієнтовану гусеницю з вершинами і діаметром, що не перевершує чотирьох, можна вкласти як підграф у будь-який турнір із вершинами. Будь-який турнір із вершинами містить як підграф будь-який з вершинами.
Пов'язані гіпотези Розенфельд висловив гіпотезу, що будь-який орієнтований шлях з вершинами (при ) можна вкласти як підграф у будь-який турнір з вершинами. Після часткових результатів, отриманих Томасоном, гіпотезу довели Аве і Томассі.
Аве і ТомассіУ статті Аве , але Аве приписує його в цій статті Томассі., у свою чергу висловив посилену гіпотезу Самнера, що будь-який турнір з вершинами містить як підграф будь-яке орієнтоване дерево з не більше ніж листками.
Берр висловив гіпотезу, що якщо граф вимагає і більше кольорів для розфарбування графа , тоді будь-яка орієнтація графа містить будь-яку орієнтацію дерева з вершинами. Оскільки повні графи вимагають різних кольорів для кожної вершини, гіпотеза Самнера випливає негайно з гіпотези БерраЦе підправлена версія гіпотези Берра зі статті Вормолда .. Як показав Берр, орієнтації графів, хроматичне число яких зростає квадратично від , є універсальними для орієнтованих дерев.
Примітки
Література
. Як процитовано у Вормолда ().
Посилання Sumner's Universal Tournament Conjecture (1971) , D. B. West, updated July 2008.