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

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

Приклади

Нехай орієнтоване дерево $P$ є зіркою $K_{1,n-1}$, в якій усі ребра орієнтовані від центра до листків. Тоді $P$ не можна вкласти в турнір, утворений із вершин регулярного $(2n-3)$-кутника шляхом спрямування всіх ребер за годинниковою стрілкою навколо многокутника. Для цього турніру будь-який напівстепінь входу і будь-який напівстепень виходу дорівнюють $n-2$, тоді як центральна вершина $P$ має більший напівстепінь виходу, $n-1$. Таким чином, якщо гіпотеза Самнера істинна, вона дає найкращий можливий розмір універсального графа для орієнтованих дерев.

Однак у будь-якому турнірі з $2n-2$ вершинами, середній напівстепінь виходу дорівнює $n-\frac{3}{2}$, а найбільший напівстепінь виходу дорівнює цілому числу, більшому або рівному середньому значенню. Таким чином, існує вершина з напівстепенем виходу $\lceil n-\frac{3}{2}\rceil =n-1$, яку можна використати як центральну вершину для копії $P$.

Часткові результати

Відомі такі часткові результати.

• Гіпотеза істинна для всіх досить великих значень $n$Шаблон:Sfn.
• Існує функція $f(n)$ з асимптотичною швидкістю зростання $f(n)=2n+o(n)$ зі властивістю, що будь-яке орієнтоване дерево з $n$ вершинами можна вкласти в підграф будь-якого турніру з $f(n)$ вершин. Крім того, і більш явно, $f(n)\le 3n-3$.
• Існує функція $g(k)$, така, що турніри з $n+g(k)$ вершинами є універсальними для орієнтованих дерев з $k$ листкамиШаблон:SfnШаблон:SfnШаблон:Sfn.
• Існує функція $h(n,\mathrm{\Delta })$, така, що будь-яке орієнтоване дерево з $n$ вершинами з найбільшим степенем, що не перевищує $\mathrm{\Delta }$, утворює підграф будь-якого турніру з $h(n,\mathrm{\Delta })$ вершинами. Якщо $\mathrm{\Delta }$ є фіксованою константою, швидкість асимптотичного зростання $h(n,\mathrm{\Delta })$ дорівнює $n+o(n)$Шаблон:Sfn.
• Будь-який «майже регулярний» турнір із $2n-2$ вершинами містить будь-яке орієнтоване дерево з $n$ вершинШаблон:Sfn.
• Будь-яку орієнтовану гусеницю з $n$ вершинами і діаметром, що не перевершує чотирьох, можна вкласти як підграф у будь-який турнір із $(2n-2)$ вершинамиШаблон:Sfn.
• Будь-який турнір із $(2n-2)$ вершинами містить як підграф будь-який Шаблон:Не перекладено з $n$ вершинамиШаблон:Sfn.

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

РозенфельдШаблон:Sfn висловив гіпотезу, що будь-який орієнтований шлях з $n$ вершинами (при $n⩾8$) можна вкласти як підграф у будь-який турнір з $n$ вершинамиШаблон:Sfn. Після часткових результатів, отриманих ТомасономШаблон:Sfn, гіпотезу довели Аве і ТомассіШаблон:Sfn.

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

БеррШаблон:Sfn висловив гіпотезу, що якщо граф $G$ вимагає $2n-2$ і більше кольорів для розфарбування графа $G$, тоді будь-яка орієнтація графа $G$ містить будь-яку орієнтацію дерева з $n$ вершинами. Оскільки повні графи вимагають різних кольорів для кожної вершини, гіпотеза Самнера випливає негайно з гіпотези Берра. Як показав Берр, орієнтації графів, хроматичне число яких зростає квадратично від $n$, є універсальними для орієнтованих дерев.

Література

• Шаблон:Книга
• Шаблон:Книга. Як процитовано у Вормолда (Шаблон:Harvard citation).
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга

Посилання

• Sumner's Universal Tournament Conjecture (1971) Шаблон:Webarchive, D. B. West, updated July 2008.