Conjecture de Sumner

Un tournoi à 6 sommets contenant un exemplaire de tout polyarbre à 4 sommets.

En théorie des graphes, la conjecture de Sumner (également appelée conjecture universelle du tournoi de Sumner), nommée ainsi d'après David Sumner, affirme que les tournois sont des graphes universels pour les polyarbres. Plus précisément tout tournoi avec $2n-2$ sommets contient tout polyarbre avec $n$ sommets comme sous-graphe.

Cette conjecture, même si elle est encore ouverte dans le cas général, a été démontré pour toutes les valeurs suffisamment grandes de $n$ par Daniela Kühn, Richard Mycroft et Deryk OsthusModèle:Sfnp.

Historique

La formulation de cette conjecture en 1971 est attribuée à David Sumner, un théoricien des graphes à l'université de Caroline du Sud. La conjecture a été prouvée pour les valeurs assez grandes de $n$ par Daniela Kühn, Richard Mycroft et Deryk OsthusModèle:Sfnp,Modèle:Sfnp.

A propos de la taille

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 $P=K_{1,n-1}$ le graphe étoile à $n$ sommets, dans lequel tous les arcs sont orientés depuis le sommet central vers les feuilles. Alors, $P$ ne peut pas être plongé comme sous-graphe dans le tournoi formé à partir des sommets d'un polygone à $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 à $n-2$, tandis que le sommet central de $P$ a un degré supérieur à $n-1$.

Cependant, dans un tournoi à $2n-2$ sommets, le degré sortant moyen est $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 $\lceil n-3/2\rceil =n-1$, qui peut être utilisé comme sommet central pour une copie de $P$.

Résultats complémentaires

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

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

Conjectures associées

Modèle:Harv a conjecturé que toute orientation d'un graphe chemin à $n\ge 8$ sommets peut être plongé comme un sous-graphe dans tout graphe à $n$ sommets. Après des résultats partiels de Modèle:Harv, elle a été prouvée par Modèle:Harv.

Havet et Thomassé à leur tour ont conjecturé un renforcement de la conjecture de Sumner, dans laquelle tout tournoi sur $n+k-1$ sommets contient comme sous-graphe tout polyarbre avec au plus $k$ feuilles. Cela a été confirmé pour presque tous les arbres par Mycroft et Modèle:Harv.

Modèle:Harv a conjecturé que si une coloration d'un graphe $G$ requiert au moins $2n-2$ couleurs, alors toute orientation de $G$ contient toute orientation d'un arbre à $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. Comme l'a montré Burr, les orientations des graphes dont le nombre chromatique croît quadratiquement en fonction de $n$ sont universelles pour les polyarbres.

Bibliographie

• Modèle:Article.
• Modèle:Article. Cité par Modèle:Harv.
• Modèle:ArticleModèle:Accès libre.
• Modèle:Article.
• Modèle:ArticleModèle:Accès libre.
• Modèle:ArticleModèle:Accès libre.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:ArticleModèle:Accès libre.
• Modèle:ArticleModèle:Accès libre.
• Modèle:Article.