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

Девід Самнер (фахівець у теорії графів із університету Південної Кароліни) 1971 року висловив гіпотезу, що турніри є універсальними графами задля полідерев^[en] (орієнтованих дерев). Точніше, гіпо́теза Са́мнера (або гіпо́теза Са́мнера про універса́льний турні́р) стверджує, що будь-яка орієнтація будь-якого дерева з ${\displaystyle n}$ вершинами є підграфом будь-якого турніру з ${\displaystyle (2n-2)}$ вершинами^[1]. Гіпотеза залишається недоведеною. Кюн, Майкрофт і Остус^[2] називають гіпотезу «однією з найвідоміших задач про турніри».

Приклади

Нехай орієнтоване дерево ${\displaystyle P}$ є зіркою ${\displaystyle K_{1,n-1}}$, в якій усі ребра орієнтовані від центра до листків. Тоді ${\displaystyle P}$ не можна вкласти в турнір, утворений із вершин регулярного ${\displaystyle (2n-3)}$-кутника шляхом спрямування всіх ребер за годинниковою стрілкою навколо многокутника. Для цього турніру будь-який напівстепінь входу і будь-який напівстепень виходу дорівнюють ${\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 n}$^[4].
• Існує функція ${\displaystyle f(n)}$ з асимптотичною швидкістю зростання ${\displaystyle f(n)=2n+o(n)}$ зі властивістю, що будь-яке орієнтоване дерево з ${\displaystyle n}$ вершинами можна вкласти в підграф будь-якого турніру з ${\displaystyle f(n)}$ вершин. Крім того, і більш явно, ${\displaystyle f(n)\leq 3n-3}$.^[5]
• Існує функція ${\displaystyle g(k)}$, така, що турніри з ${\displaystyle n+g(k)}$ вершинами є універсальними для орієнтованих дерев з ${\displaystyle k}$ листками^[6][7][8].
• Існує функція ${\displaystyle h(n,\Delta )}$, така, що будь-яке орієнтоване дерево з ${\displaystyle n}$ вершинами з найбільшим степенем, що не перевищує ${\displaystyle \Delta }$, утворює підграф будь-якого турніру з ${\displaystyle h(n,\Delta )}$ вершинами. Якщо ${\displaystyle \Delta }$ є фіксованою константою, швидкість асимптотичного зростання ${\displaystyle h(n,\Delta )}$ дорівнює ${\displaystyle n+o(n)}$^[2].
• Будь-який «майже регулярний» турнір із ${\displaystyle 2n-2}$ вершинами містить будь-яке орієнтоване дерево з ${\displaystyle n}$ вершин^[9].
• Будь-яку орієнтовану гусеницю з ${\displaystyle n}$ вершинами і діаметром, що не перевершує чотирьох, можна вкласти як підграф у будь-який турнір із ${\displaystyle (2n-2)}$ вершинами^[9].
• Будь-який турнір із ${\displaystyle (2n-2)}$ вершинами містить як підграф будь-який орієнтований кореневий граф^[en] з ${\displaystyle n}$ вершинами^[10].

Пов'язані гіпотези

Розенфельд^[11] висловив гіпотезу, що будь-який орієнтований шлях з ${\displaystyle n}$ вершинами (при ${\displaystyle n\geqslant 8}$) можна вкласти як підграф у будь-який турнір з ${\displaystyle n}$ вершинами^[9]. Після часткових результатів, отриманих Томасоном^[12], гіпотезу довели Аве і Томассі^[7].

Аве і Томассі^[13], у свою чергу висловив посилену гіпотезу Самнера, що будь-який турнір з ${\displaystyle n+k-1}$ вершинами містить як підграф будь-яке орієнтоване дерево з не більше ніж ${\displaystyle k}$ листками.

Берр^[14] висловив гіпотезу, що якщо граф ${\displaystyle G}$ вимагає ${\displaystyle 2n-2}$ і більше кольорів для розфарбування графа ${\displaystyle G}$, тоді будь-яка орієнтація графа ${\displaystyle G}$ містить будь-яку орієнтацію дерева з ${\displaystyle n}$ вершинами. Оскільки повні графи вимагають різних кольорів для кожної вершини, гіпотеза Самнера випливає негайно з гіпотези Берра^[15]. Як показав Берр, орієнтації графів, хроматичне число яких зростає квадратично від ${\displaystyle n}$, є універсальними для орієнтованих дерев.