Conjecture de Sumner

La formulation de cette conjecture en 1971 est attribuée à David Sumner, un théoricien des graphes à l'université de Caroline du Sud[2]. La conjecture a été prouvée pour les valeurs assez grandes de ${\displaystyle n}$ par Daniela Kühn, Richard Mycroft et Deryk Osthus[3],[1].

La conjecture de Sumner, si elle est prouvée, donne la plus petite taille possible d'un graphe universel, à savoir 2n-2, pour les polyarbres de taille n.

Pour le voir, considérons ${\displaystyle P=K_{1,n-1}}$ le graphe étoile à ${\displaystyle n}$ sommets, dans lequel tous les arcs sont orientés depuis le sommet central vers les feuilles. Alors, ${\displaystyle P}$ ne peut pas être plongé comme sous-graphe dans le tournoi formé à partir des sommets d'un polygone à ${\displaystyle 2n-3}$ sommets dont les arêtes sont orientées dans le sens des aiguilles d'une montre autour du polygone. En effet, dans un tel tournoi, tout sommet a un degré entrant et un degré sortant égal à ${\displaystyle n-2}$, tandis que le sommet central de ${\displaystyle P}$ a un degré supérieur à ${\displaystyle n-1}$[4].

Cependant, dans un tournoi à ${\displaystyle 2n-2}$ sommets, le degré sortant moyen est ${\displaystyle n-3/2}$, et le degré sortant maximal est un nombre entier supérieur ou égal à la moyenne. Il existe donc un sommet de degré sortant ${\displaystyle \lceil n-3/2\rceil =n-1}$, qui peut être utilisé comme sommet central pour une copie de ${\displaystyle P}$.

Les résultats suivants sur la conjecture ont été prouvés.

• Il existe une fonction ${\displaystyle f(n)}$ avec taux de croissance asymptotique ${\displaystyle f(n)=2n+o(n)}$ avec la propriété que tout polyarbre à ${\displaystyle n}$ sommets peut être plongé comme sous-graphe dans tout tournoi à ${\displaystyle f(n)}$ sommets. De plus, on a la majoration ${\displaystyle f(n)\leq 3n-3}$[5].
• Il existe une fonction ${\displaystyle g(k)}$ telle que les tournois sur ${\displaystyle n+g(k)}$ les sommets sont universels pour les polyarbres à ${\displaystyle k}$ feuilles[6].
• Il existe une fonction ${\displaystyle h(n,\Delta )}$ telle que tout polyarbre à ${\displaystyle n}$ sommets de degré au plus ${\displaystyle \Delta }$ peut être plongé comme sous-graphe dans tout tournoi à ${\displaystyle h(n,\Delta )}$ sommets. Lorsque ${\displaystyle \Delta }$ est une constante fixe, le taux de croissance asymptotique de ${\displaystyle h(n,\Delta )}$ est ${\displaystyle n+o(n)}$[3].
• Tout tournoi « quasi régulier » sur ${\displaystyle 2n-2}$ sommets contient chaque polyarbre à ${\displaystyle n}$ sommets[7].
• Tout graphe chenille orienté à ${\displaystyle n}$ sommets de diamètre au plus 4 peut être plongé comme sous-graphe dans tout tournoi à ${\displaystyle 2n-2}$ sommets[7].
• Tout tournoi à ${\displaystyle 2n-2}$ sommets contient comme sous-graphe toute arborescence à ${\displaystyle n}$ sommets[8].

(Rosenfeld 1972) a conjecturé que toute orientation d'un graphe chemin à ${\displaystyle n\geq 8}$ sommets peut être plongé comme un sous-graphe dans tout graphe à ${\displaystyle n}$ sommets. Après des résultats partiels de (Thomason 1986), elle a été prouvée par (Havet et Thomassé 2000a).

Havet et Thomassé[9] à leur tour ont conjecturé un renforcement de la conjecture de Sumner, dans laquelle tout tournoi sur ${\displaystyle n+k-1}$ sommets contient comme sous-graphe tout polyarbre avec au plus ${\displaystyle k}$ feuilles. Cela a été confirmé pour presque tous les arbres par Mycroft et (Naia 2018).

(Burr 1980) a conjecturé que si une coloration d'un graphe ${\displaystyle G}$ requiert au moins ${\displaystyle 2n-2}$ couleurs, alors toute orientation de ${\displaystyle G}$ contient toute orientation d'un arbre à ${\displaystyle n}$ sommets. Comme les graphes complets nécessitent une couleur différente pour chaque sommet, la conjecture de Sumner découle immédiatement de la conjecture de Burr[10]. Comme l'a montré Burr, les orientations des graphes dont le nombre chromatique croît quadratiquement en fonction de ${\displaystyle n}$ sont universelles pour les polyarbres.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sumner's conjecture » (voir la liste des auteurs).

• Stefan A. Burr, « Subtrees of directed graphs and hypergraphs », Congressus Numerantium, vol. 28 « Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing »,‎ 1980, p. 227–239 (MR 608430).
• Fan R. K. Chung, « A note on subtrees in tournaments », Internal Memorandum, Bell Laboratories,‎ 1981. Cité par (Wormald 1983).
• A. El Sahili, « Trees in tournaments », Journal of Combinatorial Theory, Series B, vol. 92, n^o 1,‎ 2004, p. 183–187 (DOI 10.1016/j.jctb.2004.04.002, MR 2078502).
• Roland Häggkvist et Andrew Thomason, « Trees in tournaments », Combinatorica, vol. 11, n^o 2,‎ 1991, p. 123–130 (DOI 10.1007/BF01206356, MR 1136161).
• Frédéric Havet, « Trees in tournaments », Discrete Mathematics, vol. 243, n^os 1-3,‎ 2002, p. 121–134 (DOI 10.1016/S0012-365X(00)00463-5, MR 1874730).
• Frédéric Havet et Stéphan Thomassé, « Oriented Hamiltonian paths in tournaments: a proof of Rosenfeld's conjecture », Journal of Combinatorial Theory, série B, vol. 78, n^o 2,‎ 2000a, p. 243–273 (DOI 10.1006/jctb.1999.1945, MR 1750898).
• Frédéric Havet et Stéphan Thomassé, « Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture », Journal of Graph Theory, vol. 35, n^o 4,‎ 2000b, p. 244–256 (DOI 10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H, MR 1791347).
• Daniela Kühn, Richard Mycroft et Deryk Osthus, « An approximate version of Sumner's universal tournament conjecture », Journal of Combinatorial Theory, Series B, vol. 101, n^o 6,‎ 2011a, p. 415–447 (DOI 10.1016/j.jctb.2010.12.006, MR 2832810, zbMATH 1234.05115, arXiv 1010.4429).
• Daniela Kühn, Richard Mycroft et Deryk Osthus, « A proof of Sumner's universal tournament conjecture for large tournaments », Proceedings of the London Mathematical Society, Third Series, vol. 102, n^o 4,‎ 2011b, p. 731–766 (DOI 10.1112/plms/pdq035, MR 2793448, zbMATH 1218.05034, arXiv 1010.4430).
• Tássio Naia, Large structures in dense directed graphs (Thèse de doctorat), University of Birmingham, 2018 (lire en ligne).
• K. B. Reid et N. C. Wormald, « Embedding oriented n-trees in tournaments », Studia Scientiarum Mathematicarum Hungarica, vol. 18, n^os 2-4,‎ 1983, p. 377–387 (MR 787942).
• M. Rosenfeld, « Antidirected Hamiltonian paths in tournaments », Journal of Combinatorial Theory, série B, vol. 12,‎ 1972, p. 93–99 (DOI 10.1016/0095-8956(72)90035-4, MR 0285452).
• Andrew Thomason, « Paths and cycles in tournaments », Transactions of the American Mathematical Society, vol. 296, n^o 1,‎ 1986, p. 167–180 (DOI 10.2307/2000567, MR 837805).
• Nicholas C. Wormald, « Subtrees of large tournaments », Lecture Notes in Math., Berlin, Springer, vol. 1036 « Combinatorial mathematics, X (Adelaide, 1982) »,‎ 1983, p. 417–419 (DOI 10.1007/BFb0071535, MR 731598).