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

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

Приклади

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

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

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

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

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

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

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

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

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

Література

• Stefan A. Burr. Subtrees of directed graphs and hypergraphs // Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1980), Vol. I. — 1980. — Т. 28. — С. 227—239. — (Congressus Numerantium)
• Chung F.R.K. A note on subtrees in tournaments. — Bell Laboratories, 1981. — (Internal Memorandum). Як процитовано у Вормолда ((Wormald, 1983)).
• El Sahili A. Trees in tournaments // Journal of Combinatorial Theory. — 2004. — Т. 92 (5 листопада). — С. 183—187. — (1). — DOI:10.1016/j.jctb.2004.04.002.
• Roland Häggkvist, Andrew Thomason. Trees in tournaments // Combinatorica. — 1991. — Т. 11 (5 листопада). — С. 123—130. — (2). — DOI:10.1007/BF01206356.
• Frédéric Havet. Trees in tournaments // Discrete Mathematics. — 2002. — Т. 243 (5 листопада). — С. 121—134. — (1-3). — DOI:10.1016/S0012-365X(00)00463-5.
• Frédéric Havet, Stéphan Thomassé. Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture // Journal of Combinatorial Theory. — 2024. — Т. 78 (5 листопада). — С. 243—273. — (2). — DOI:10.1006/jctb.1999.1945.
• Frédéric Havet, Stéphan Thomassé. Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture // Journal of Graph Theory. — 2024. — Т. 35 (5 листопада). — С. 244—256. — (4). — DOI:10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H.
• Daniela Kühn, Richard Mycroft, Deryk Osthus. An approximate version of Sumner's universal tournament conjecture // Journal of Combinatorial Theory. — 2024. — Т. 101 (5 листопада). — С. 415—447. — (6). — DOI:10.1016/j.jctb.2010.12.006.
• Daniela Kühn, Richard Mycroft, Deryk Osthus. A proof of Sumner's universal tournament conjecture for large tournaments // Proceedings of the London Mathematical Society. — 2024. — Т. 102, вип. 4 (5 листопада). — С. 731—766. — (Third Series). — arXiv:1010.4430. — DOI:10.1112/plms/pdq035.
• Embedding oriented n-trees in tournaments // Studia Scientiarum Mathematicarum Hungarica. — 1983. — Т. 18 (5 листопада). — С. 377—387. — (2-4).
• Rosenfeld M. Antidirected Hamiltonian paths in tournaments // Journal of Combinatorial Theory. — 1972. — Т. 12 (5 листопада). — С. 93—99. — (Series B). — DOI:10.1016/0095-8956(72)90035-4.
• Andrew Thomason. Paths and cycles in tournaments // Transactions of the American Mathematical Society. — 1986. — Vol. 296 (5 November). — P. 167—180. — (1). — DOI:10.2307/2000567.
• Nicholas C. Wormald. Combinatorial mathematics, X (Adelaide, 1982). — Berlin : Springer, 1983. — Т. 1036. — С. 417—419. — (Lecture Notes in Math.) — DOI:10.1007/BFb0071535.

Посилання

• Sumner's Universal Tournament Conjecture (1971) [Архівовано 27 лютого 2014 у Wayback Machine.], D. B. West, updated July 2008.