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

Девід Самнер (фахівець у теорії графів із університету Південної Кароліни) 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}$, є універсальними для орієнтованих дерев.

Примітки

1. (Kühn, Mycroft, Osthus, 2011a). Найраніша опублікована цитата, яку навела Даніела Кюн та ін. надлежить Райду і Вормолду ((Reid, Wormald, 1983), (Wormald, 1983)). Вормолд цитує гіпотезу як почуту в приватній бесіді зі Самнером.
2. Kühn, Mycroft, Osthus, 2011a.
3. Цей приклад взято зі статті Кюн, Майкрофта і Остуса ((Kühn, Mycroft, Osthus, 2011a)).
4. Kühn, Mycroft, Osthus, 2011b.
5. Kühn, Mycroft, Osthus, 2011a; El Sahili, 2004. Более слабые и полученные ранее границы для функции ${\displaystyle f(n)}$ можно найти в статьях Chung, 1981, Wormald, 1983, Häggkvist, Thomason, 1991, Havet, Thomassé, 2000b, Havet, 2002.
6. Häggkvist, Thomason, 1991.
7. Havet, Thomassé, 2000a.
8. Havet, 2002.
9. Reid, Wormald, 1983.
10. Havet, Thomassé, 2000b.
11. Rosenfeld, 1972.
12. Thomason, 1986.
13. У статті Аве (Havet, 2002), але Аве приписує його в цій статті Томассі.
14. Burr, 1980.
15. Це підправлена версія гіпотези Берра зі статті Вормолда (Wormald, 1983).

Література

• 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 (25 грудня). — С. 183—187. — (1). — DOI:10.1016/j.jctb.2004.04.002.
• Roland Häggkvist, Andrew Thomason. Trees in tournaments // Combinatorica. — 1991. — Т. 11 (25 грудня). — С. 123—130. — (2). — DOI:10.1007/BF01206356.
• Frédéric Havet. Trees in tournaments // Discrete Mathematics. — 2002. — Т. 243 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 731—766. — (Third Series). — arXiv:1010.4430. — DOI:10.1112/plms/pdq035.
• Embedding oriented n-trees in tournaments // Studia Scientiarum Mathematicarum Hungarica. — 1983. — Т. 18 (25 грудня). — С. 377—387. — (2-4).
• Rosenfeld M. Antidirected Hamiltonian paths in tournaments // Journal of Combinatorial Theory. — 1972. — Т. 12 (25 грудня). — С. 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 (25 December). — 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.