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

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

Приклади ред.

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

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

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

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

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

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

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

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

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

Примітки ред.

↑ (Kühn, Mycroft, Osthus, 2011a). Найраніша опублікована цитата, яку навела Даніела Кюн та ін. надлежить Райду і Вормолду ((Reid, Wormald, 1983), (Wormald, 1983)). Вормолд цитує гіпотезу як почуту в приватній бесіді зі Самнером.
↑ ^а ^б Kühn, Mycroft, Osthus, 2011a.
↑ Цей приклад взято зі статті Кюн, Майкрофта і Остуса ((Kühn, Mycroft, Osthus, 2011a)).
↑ Kühn, Mycroft, Osthus, 2011b.
↑ (Kühn, Mycroft, Osthus, 2011a); (El Sahili, 2004). Более слабые и полученные ранее границы для функции $f(n)$ можно найти в статьях (Chung, 1981), (Wormald, 1983), (Häggkvist, Thomason, 1991), (Havet, Thomassé, 2000b), (Havet, 2002).
↑ Häggkvist, Thomason, 1991.
↑ ^а ^б Havet, Thomassé, 2000a.
↑ Havet, 2002.
↑ ^а ^б ^в Reid, Wormald, 1983.
↑ Havet, Thomassé, 2000b.
↑ Rosenfeld, 1972.
↑ Thomason, 1986.
↑ У статті Аве (Havet, 2002), але Аве приписує його в цій статті Томассі.
↑ Burr, 1980.
↑ Це підправлена версія гіпотези Берра зі статті Вормолда (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 (4 квітня). — С. 183—187. — (1). — DOI:10.1016/j.jctb.2004.04.002.
Roland Häggkvist, Andrew Thomason. Trees in tournaments // Combinatorica. — 1991. — Т. 11 (4 квітня). — С. 123—130. — (2). — DOI:10.1007/BF01206356.
Frédéric Havet. Trees in tournaments // Discrete Mathematics. — 2002. — Т. 243 (4 квітня). — С. 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 (4 квітня). — С. 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 (4 квітня). — С. 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 (4 квітня). — С. 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 (4 квітня). — С. 731—766. — (Third Series). — arXiv:1010.4430. — DOI:10.1112/plms/pdq035.
Embedding oriented n-trees in tournaments // Studia Scientiarum Mathematicarum Hungarica. — 1983. — Т. 18 (4 квітня). — С. 377—387. — (2-4).
Rosenfeld M. Antidirected Hamiltonian paths in tournaments // Journal of Combinatorial Theory. — 1972. — Т. 12 (4 квітня). — С. 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 (4 April). — 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.

[1] (Kühn, Mycroft, Osthus, 2011a). Найраніша опублікована цитата, яку навела Даніела Кюн та ін. надлежить Райду і Вормолду ((Reid, Wormald, 1983), (Wormald, 1983)). Вормолд цитує гіпотезу як почуту в приватній бесіді зі Самнером.

[FOOTNOTEKühn,_Mycroft,_Osthus2011a-2] а ^б Kühn, Mycroft, Osthus, 2011a.

[3] Цей приклад взято зі статті Кюн, Майкрофта і Остуса ((Kühn, Mycroft, Osthus, 2011a)).

[FOOTNOTEKühn,_Mycroft,_Osthus2011b-4] Kühn, Mycroft, Osthus, 2011b.

[5] (Kühn, Mycroft, Osthus, 2011a); (El Sahili, 2004). Более слабые и полученные ранее границы для функции $f(n)$ можно найти в статьях (Chung, 1981), (Wormald, 1983), (Häggkvist, Thomason, 1991), (Havet, Thomassé, 2000b), (Havet, 2002).

[FOOTNOTEHäggkvist,_Thomason1991-6] Häggkvist, Thomason, 1991.

[FOOTNOTEHavet,_Thomassé2000a-7] а ^б Havet, Thomassé, 2000a.

[FOOTNOTEHavet2002-8] Havet, 2002.

[FOOTNOTEReid,_Wormald1983-9] а ^б ^в Reid, Wormald, 1983.

[FOOTNOTEHavet,_Thomassé2000b-10] Havet, Thomassé, 2000b.

[FOOTNOTERosenfeld1972-11] Rosenfeld, 1972.

[FOOTNOTEThomason1986-12] Thomason, 1986.

[13] У статті Аве (Havet, 2002), але Аве приписує його в цій статті Томассі.

[FOOTNOTEBurr1980-14] Burr, 1980.

[15] Це підправлена версія гіпотези Берра зі статті Вормолда (Wormald, 1983).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]