Théorème de Robertson-Seymour

En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour affirme qu'un certain classement partiel entre graphes non orientés possède des propriétés remarquables (c'est un bel ordre). Ce théorème a pour conséquence qu'il devient possible de caractériser de nombreuses familles de graphes par une liste finie de graphes qu’elles ne contiennent pas. Ce théorème généralise ainsi le théorème de Kuratowski, qui caractérise les graphes planaires comme ceux ne contenant pas deux graphes particuliers.

Le théorème de Robertson–Seymour est également appelé le théorème des mineurs, car le classement partiel évoqué dans son énoncé est défini par la relation « être un mineur ». Le théorème équivaut ainsi à dire que toute famille F de graphes fermée, c'est-à-dire telle que les mineurs des graphes de F appartiennent aussi à F, peut être caractérisée par un ensemble fini de « mineurs exclus ».

Connu, avant qu'il soit démontré, sous le nom de conjecture de Wagner, ce théorème, démontré en 2004 par Neil Robertson et Paul Seymour, est considéré généralement comme un des résultats les plus importants de la théorie des graphes. Il a une démonstration extrêmement complexe et délicate, dont la publication, comportant plus de cinq cents pages, s'étale de 1983 à 2004 dans vingt articles de la revue Journal of Combinatorial Theory.

Le théorème n'est pas constructif (on ne connait d'ailleurs les listes explicites de mineurs exclus que dans très peu de cas), mais Robertson et Seymour ont montré qu'il a d'importantes conséquences en théorie de la complexité, car il garantit l'existence d'algorithmes rapides pour de nombreux problèmes de décision.

Présentation informelle du théorème

Un célèbre exemple historique : la modélisation par Euler du problème des ponts de Königsberg.
plan de la ville de Königsberg (à l'époque d'Euler)

→

le réseau des sept ponts de la ville →

le graphe modélisant le problème des ponts

La théorie des graphes est la discipline mathématique (et informatique) qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des points[note 1]. Ces modèles sont constitués par la donnée de « points », appelés des sommets (en référence aux polyèdres), et de « liens » entre ces points ; ces liens, pour les graphes étudiés ici, sont symétriques (les graphes sont dits non orientés) et sont appelés des arêtes.

Un graphe ne peut pas toujours être dessiné sur une feuille de papier (ou, plus rigoureusement, dans un plan) sans que les arêtes se coupent ; quand c'est possible, le graphe est alors dit planaire. Ainsi, l'explication de l'impossibilité de l'énigme des trois maisons est que le graphe qui modélise l'énigme n'est pas planaire. En 1930, Kuratowski a obtenu une caractérisation de tous les graphes planaires, légèrement reformulée quelques années plus tard par Wagner, sous la forme d'une liste de deux graphes ne devant pas être « contenus » dans un graphe donné[note 2] pour que ce dernier soit planaire.

Ce graphe à 14 sommets et 21 arêtes ne peut être tracé sur une feuille de papier sans que ses arêtes se coupent (il n'est pas planaire), mais peut être ainsi tracé sur un tore (un pneu) : on dit que c'est un graphe toroïdal.

Les deux mineurs exclus des graphes planaires.
Le graphe complet $K_{5}$ , ayant 5 sommets et 10 arêtes.
Le graphe biparti complet $K_{3,3}$ , ayant 6 sommets et 9 arêtes.

Pour de nombreuses familles de graphes, par exemple ceux pouvant être dessinés sur la surface d'un pneu (en mathématiques, on parle de tore, et les graphes ainsi traçables sont les graphes toroïdaux), on peut se demander s'il existe une caractérisation analogue ; le théorème de Robertson-Seymour apporte une réponse affirmative. Ce théorème montre qu'un certain classement (partiel) entre les graphes possède des propriétés remarquables (c'est un bel ordre). On en déduit que pour toute famille de graphes « fermée pour les mineurs » (le sens technique exact de cette expression sera détaillé plus loin), il existe une liste finie de graphes « interdits » caractérisant cette famille. Cependant, même pour des familles simples comme celle des graphes toroïdaux, cette liste peut être très longue, et on ne connaît pas en général de méthode explicite pour la construire.

Historique

En 1930, Kazimierz Kuratowski démontrait[1] qu'un graphe était planaire s'il ne contenait pas de sous-graphe qui soit une expansion[note 3] du graphe complet K₅, ou du graphe biparti complet K_3,3[note 4].

En 1937[2], Klaus Wagner donnait une forme analogue et d'ailleurs équivalente[3] de ce théorème, en caractérisant ces graphes comme ne contenant ni K₅ ni K_3,3 comme « mineurs ». Cette forme permet une généralisation facile à de nombreuses familles de graphes ayant une propriété analogue[note 5], par exemple « être traçable sur un tore », c'est pourquoi le théorème des mineurs, avant sa démonstration, était connu sous le nom de conjecture de Wagner (cependant, Wagner a par la suite affirmé qu'il n'avait jamais formulé lui-même cette conjecture, et avait d'ailleurs toujours pensé qu'elle devait être fausse[4]).

Un résultat plus faible que cette conjecture, concernant seulement les arbres, découle du théorème de Kruskal[note 6], lequel avait été conjecturé en 1937 par Andrew Vázsonyi ; il fut démontré indépendamment en 1960 par Joseph Kruskal[5] et S. Tarkowski[6].

Entre 1983 et 2004, Neil Robertson et Paul Seymour développèrent sur une série de vingt articles publiés dans la revue Journal of Combinatorial Theory un plan de démonstration complet consistant entre autres à réduire progressivement le cas général à des cas particuliers plus simples[note 7] (ainsi, le premier de leurs articles s'intitule Mineurs : exclusion d'une forêt et donne une démonstration d'une vingtaine de pages de ce que si l'un des mineurs exclus est une forêt[note 8], le théorème est vrai[7]), mais introduisant également de nombreux concepts et outils nouveaux, comme la théorie de la décomposition arborescente[8]. L'ensemble de la démonstration couvre au total plus de 500 pages[note 9] ; la communauté mathématique en a validé le résultat[note 10], appelé désormais théorème de Robertson-Seymour[9], pour lequel ils reçurent en 2006 le prix Fulkerson[8] ; ce théorème, les outils développés pour sa démonstration, et ses conséquences algorithmiques inattendues, sont généralement considérés comme parmi les plus importants de la théorie des graphes[10].

Le théorème de Robertson-Seymour

Définitions préliminaires

Diagramme représentant deux graphes, l'un étant un mineur de l'autre

Un exemple de deux graphes, dont l'un (celui du dessous) est un mineur de l'autre. Le mineur a été obtenu en supprimant l'arête [e,f] et en contractant l'arête [b,c].

Un mineur d'un graphe non orienté G est un graphe pouvant être obtenu à partir de G par une suite (éventuellement vide) de contractions d'arêtes de G, de suppressions d'arêtes de G, et de suppressions de sommets isolés de G[11] - [note 11].

La relation « H est un mineur de G » (qu'on notera par la suite H ≤ G) est une relation d'ordre partiel sur l'ensemble des graphes non orientés finis, considérés à isomorphisme près[note 12] (si l'on ne considère pas les graphes isomorphes comme identiques, la relation n'est plus antisymétrique, et on obtient seulement un préordre[12]).

Un préordre est appelé un beau préordre s'il ne contient aucune suite infinie strictement décroissante (on dit que la relation de préordre est bien fondée), ni aucune antichaîne infinie, c'est-à-dire aucun ensemble infini d'éléments incomparables deux à deux ; dans le cas d'un ordre (partiel), on dit que c'est un bel ordre[note 13] (cette définition généralise aux ordres partiels la notion de bon ordre définie pour les ensembles totalement ordonnés).

Énoncés du théorème

Les définitions précédentes permettent de formuler rigoureusement le

Théorème de Robertson–Seymour — La relation de préordre « F ≤ G si et seulement si F est un mineur de G » est un beau préordre sur l'ensemble des graphes non orientés finis.

L'existence d'une suite infinie strictement décroissante étant évidemment impossible (puisque chaque mineur contient alors moins d'arêtes que le graphe précédent[13]), ce théorème revient donc à affirmer qu'il n'y a pas d'ensemble infini de graphes deux à deux incomparables par la relation ≤ ; il convient cependant de remarquer que le théorème n'exclut nullement qu'il existe de tels ensembles finis aussi grands que l'on veut[note 14].

Utilisant la notion de graphe minimal d'un ensemble, c'est-à-dire tel qu'aucun autre graphe de l'ensemble n'en soit un mineur, on arrive à un énoncé équivalent au théorème, affirmant que dans tout ensemble de graphes, il n'y a (à isomorphisme près) qu'un nombre fini de graphes minimaux ; comme on le verra plus loin, cela revient à caractériser toute famille F « fermée pour les mineurs » par un ensemble fini S de mineurs exclus[note 15].

Dire qu'il n'existe pas d'antichaînes infinies revient, par définition, à dire que dans tout ensemble infini de graphes, il existe un couple de graphes dont l'un est un mineur de l'autre[13] ; un résultat plus précis, et qui est en fait une propriété équivalente au théorème de Robertson-Seymour[note 16], couvre également l'impossibilité de suites infinies décroissantes, et affirme que toute suite infinie $G_{i}$ de graphes contient un couple $\scriptstyle (G_{i},G_{j})$ tel que i < j et que $G_{i}$ est un mineur de $G_{j}$ [14].

Éléments de la démonstration

La preuve du théorème repose sur une série de résultats publiés entre 1983 et 2004 sous le titre Graph Minors, et dont l'enchaînement est résumé dans l'article Graph Minors XX, mettant un point final à la démonstration[15]. Tous les résultats obtenus dans cette suite de vingt articles ne sont pas nécessaires à la preuve finale[note 7], mais une rédaction complète de celle-ci demanderait encore plusieurs centaines de pages[16] ; il est difficile ne serait-ce que d'esquisser les grandes lignes d'une démonstration aussi complexe[17].

Les deux idées essentielles utilisées par Robertson et Seymour sont, d'une part, la notion de structuration de graphe : il s'agit de techniques consistant à décrire un graphe comme composé (le plus souvent par « recollement ») de graphes plus simples[note 17] ; d'autre part, l'utilisation de considérations topologiques sur les surfaces sur lesquelles un graphe peut être plongé.

La description plus détaillée qui suit est essentiellement adaptée de celle de Reinhard Diestel[18], qui suit assez étroitement la démonstration originale, en la simplifiant quelque peu.

En utilisant les propriétés des beaux ordres, on se ramène d'abord à l'étude d'une famille infinie de graphes n'admettant pas le graphe complet K_n comme mineur ;
On montre ensuite qu'il existe un ensemble fini de surfaces S_k tel que les graphes de la famille étudiée sont « presque » plongeables dans l'une des S_k[note 18], alors que K_n ne s'y plonge pas.
La conclusion résulte alors d'un raisonnement par récurrence sur le genre des surfaces S_k (leur nombre de « trous »), la base de la récurrence étant, justement, le théorème de Wagner sur les graphes planaires : une décomposition arborescente convenable d'un graphe plongé sur une surface permet de se ramener à une surface de genre inférieur (en « comblant les trous ») sans trop modifier le graphe[note 19].

Familles fermées pour les mineurs

Une famille F de graphes est dite fermée (ou close) pour les mineurs (ce qui sera abrégé en famille fermée dans le reste de cet article) si chaque mineur d'un graphe de F appartient également à F[note 20]. Dans le langage de la théorie des ordres, une famille fermée est donc une section commençante pour la relation « être un mineur ».

Caractérisation par mineurs exclus

Si F est une famille fermée, appelons S l'ensemble des graphes qui ne sont pas dans F (le complémentaire de F). Le théorème de Robertson–Seymour affirme l'existence d'un ensemble fini H formé des éléments minimaux de S[note 21]. Ces éléments minimaux caractérisent F : les graphes de F sont exactement ceux n'admettant aucun graphe de H comme mineur[19]. Les éléments de H sont appelés les mineurs exclus (ou interdits), ou encore les obstructions[note 22], pour la famille F.

Ainsi, les graphes planaires forment une famille fermée : les contractions et les suppressions d'arêtes d'un graphe planaire ne peuvent détruire sa planarité. Il en résulte que ces graphes peuvent être caractérisés par une famille finie de mineurs exclus, qui sont dans ce cas les deux graphes du théorème de Wagner : le graphe complet K₅ et le graphe biparti complet K_3,3.

L'existence d'une caractérisation par mineurs exclus de toutes les familles fermées est une affirmation équivalente au théorème de Robertson-Seymour. En effet, si S est un ensemble de graphes, appelons F la famille des graphes n'ayant pas de mineurs dans S. F est alors fermée, et son ensemble H de mineurs exclus est exactement l'ensemble des éléments minimaux de S (incomparables deux à deux), ce qui prouve que cet ensemble est fini[20].

Exemples de familles fermées

Diagramme représentant les sept graphes de la famille de Petersen, ainsi que leurs relations

La famille de Petersen, ensemble des sept obstructions correspondant aux graphes pouvant être plongés dans l'espace sans entrelacements[note 23] (ces graphes sont incomparables en tant que mineurs, mais reliés les uns aux autres (comme indiqué par les traits bleus) par les transformations Y-Δ du théorème de Kennelly).

Les familles de graphes (finis) suivantes[note 24] sont fermées pour les mineurs, et par conséquent (d'après le théorème de Robertson–Seymour) possèdent des caractérisations par mineurs exclus (mais qu'on ne connait pas explicitement en général) :

les forêts (les graphes qui sont des unions d'arbres disjoints) ; on remarquera que les arbres eux-mêmes ne forment pas une famille fermée, un mineur d'un arbre n'étant pas forcément connexe ;
les graphes planaires, les graphes toroïdaux, et, plus généralement, les graphes qui peuvent être tracés sur une surface donnée[21] ;
les graphes qui peuvent être plongés sans entrelacement[note 23] ou sans nœud dans l'espace euclidien à 3 dimensions[21] ;
les graphes dont certains invariants[note 25], tels que la largeur arborescente ou la taille du coupe-cycles de sommets minimum, sont bornés par une constante finie fixée[note 26].

Ensembles d'obstructions

L’ensemble des obstructions pour une famille F donnée est défini comme l'ensemble des éléments minimaux (pour la relation de mineurs) du complémentaire de F, c'est-à-dire que c'est le plus petit ensemble de mineurs exclus caractérisant F ; le théorème de Robertson-Seymour affirme que cet ensemble est toujours fini quelle que soit F.

Des exemples d'ensembles d'obstructions finis étaient déjà connus (pour des classes de graphes particuliers) avant que le théorème de Robertson–Seymour soit démontré. Ainsi, la famille des forêts[note 8] a pour seule obstruction le cycle à trois sommets (si l'on se restreint aux graphes simples), c'est-à-dire qu'un graphe est une forêt si et seulement s'il n'a pas ce cycle pour mineur. De même, le théorème de Wagner dit que l'ensemble des obstructions pour les graphes planaires est {K₅, K_3,3}. Un théorème analogue caractérise les graphes planaires extérieurs comme ayant pour obstructions les graphes K₄ et K_2,3.

Le théorème de Robertson-Seymour étend ces résultats à des familles fermées quelconques, mais, étant extrêmement non constructif, ne permet le plus souvent pas, même en principe[note 27], de déterminer l'ensemble des obstructions d'une famille donnée. Par exemple, l'ensemble des graphes toroïdaux (traçables sur un tore) est une famille fermée dont on ignore l'ensemble des obstructions ; on sait seulement qu'il comporte au moins 17 000 graphes[22]. En 2020, on ne connait complètement l'ensemble des obstructions pour les familles de graphes traçables sur une surface donnée que dans le cas du plan (les deux graphes mentionnés plus haut) et dans le cas du plan projectif, où cet ensemble comporte 35 graphes[23] - [note 28].

Algorithmes liés au théorème des mineurs

De nombreuses questions d'informatique théorique sont modélisées par des graphes, ou plus précisément par la détermination de propriétés de certains graphes, un exemple célèbre étant le problème du voyageur de commerce.

La démonstration du théorème des mineurs a complètement changé l'estimation qu'on avait de la difficulté algorithmique de certains de ces problèmes. Ainsi, on ignorait jusque-là si la question de savoir si un graphe peut être plongé sans nœuds dans l'espace usuel était calculable, c'est-à-dire décidable par une machine de Turing ; on sait désormais qu'en fait, ce problème appartient à la classe P des problèmes solubles en temps polynomial, bien qu'on ne connaisse toujours aucun algorithme (même très lent) pour le résoudre[24].

Reconnaissance en temps polynomial

Robertson et Seymour ont démontré que pour tout graphe fixé G, il existe un algorithme en temps polynomial qui teste si un graphe quelconque H possède G comme mineur[25]. Plus précisément, cet algorithme demande un temps proportionnel au cube du nombre n des sommets et arêtes du graphe testé H (ce que l'on note $O(n^{3})$ en notation de Landau). Ce résultat est moins utile en pratique qu'on ne pourrait le croire, parce que la constante de proportionnalité croît avec la taille de G de manière exponentielle. Il en résulte cependant que, pour toute famille fermée F, il existe un algorithme en temps polynomial décidant si un graphe donné G appartient ou non à F : il suffit de contrôler, pour chaque élément de l'ensemble des obstructions de F, s'il est ou non un mineur de G.

L'existence de cet algorithme est donc une conséquence du théorème de Robertson-Seymour, mais ce dernier ne donne aucun moyen effectif de le construire ; il est ainsi possible de démontrer qu'un problème peut être résolu en temps polynomial (dans le langage de la théorie de la complexité, on dit qu'il appartient à la classe P) sans pouvoir exhiber une telle solution : on dit qu'une telle preuve est non constructive[26]. En revanche, dans de nombreux cas où l'ensemble des obstructions de F est connu explicitement, il est possible de savoir si un graphe appartient à F de manière plus efficace encore ; ainsi, tester si un graphe à n sommets est planaire peut être fait en temps linéaire[27], c'est-à-dire en temps proportionnel à n.

Pour des invariants de graphes[note 25] ayant la propriété que, pour un k fixé, la famille des graphes d'invariant plus petit que k est fermée[note 26], le même théorème s'applique ; c'est par exemple le cas de la largeur arborescente, ou du genre minimal de la surface sur laquelle le graphe peut être tracé. Dans chacun de ces cas, pour chaque k fixé, il y a un algorithme permettant, pour un graphe G ayant n sommets et arêtes, de déterminer si son invariant est ou non inférieur à k, en un temps inférieur à $C(k)n^{3}$ , où $C(k)$ est une constante ne dépendant que de k et de l'invariant mesuré. Un problème ayant cette propriété (où $n^{3}$ est remplacé par un polynôme quelconque) est dit soluble à paramètre fixé.

Cependant, cette méthode ne permet pas de construire un algorithme unique permettant de déterminer la valeur d'un tel invariant pour un graphe donné (lorsque cette valeur n'est pas bornée à l'avance), à cause de la difficulté qu'il y a à déterminer l'ensemble des obstructions. De plus, la constante $C(k)$ augmente en général extrêmement vite avec k, rendant ces algorithmes très inefficaces en pratique. C'est pourquoi le développement d'algorithmes plus efficaces pour ces problèmes constitue encore en 2020 un important domaine de recherche.

Relation avec le problème P ≟ NP

Le théorème des mineurs semble permettre de construire des algorithmes rapides (polynomiaux, et même cubiques) de résolution de problèmes dont on sait qu'ils sont NP-complets, voire NP-difficiles[28]. Cependant, une analyse plus précise de la définition de la complexité des algorithmes[note 29] montre que ces algorithmes prennent en fait un temps exponentiel par rapport à la taille des graphes décrivant le problème à résoudre. Ainsi, le problème des chemins disjoints est NP-complet[note 30], mais Robertson et Seymour ont montré que, à k fixé, le problème des k chemins disjoints est effectivement soluble en temps polynomial[29] ; cette contradiction apparente[note 31] se résout en remarquant que le temps pris par l'algorithme est un polynôme en n (la taille du graphe étudié) de la forme $C(k)n^{3}$ , comme on l'a vu dans la section précédente, mais que la constante $C(k)$ augmente au moins exponentiellement avec k, et que c'est elle qui définit la complexité du problème lorsque k est inconnu.

Bien que le théorème de Robertson-Seymour n'ait pas vraiment apporté d'informations nouvelles concernant le problème P ≟ NP, Fellows et Langston ont fait remarquer[30] que leur démonstration non constructive d'existence d'algorithmes polynomiaux (et où apparaissent souvent, qui plus est, des constantes de proportionnalité bien trop grandes pour qu'ils puissent avoir une utilité pratique quelconque) rend moins claire qu'auparavant la distinction entre algorithmes polynomiaux (considérés comme utilisables de manière réaliste) et non polynomiaux (à jamais inutilisables pour des ensembles de données un peu vastes), et donc que l'intuition de la majorité des informaticiens[note 32], selon laquelle la classe P est différente de la classe NP, pourrait bien se révéler fausse, sans pour autant que les problèmes NP-complets en deviennent faciles à résoudre.

Conséquences en logique mathématique

L'étude de la logique mathématique, c'est-à-dire l'analyse systématique des fondations des mathématiques et des bases logiques sur lesquelles s'appuient les démonstrations, commencée à la fin du dix-neuvième siècle par des logiciens et des mathématiciens tels que Gottlob Frege et Giuseppe Peano, a amené vers 1930 à la découverte de surprenants résultats d'indécidabilité, liés aux célèbres théorèmes d'incomplétude de Gödel ; ces résultats, dont la forme générale est « la théorie T ne permet, pour un certain énoncé E exprimable dans son langage, ni de démontrer E, ni de démontrer sa négation non E », sont souvent dits méta-mathématiques, car ils portent sur les mathématiques elles-mêmes et non sur les objets mathématiques usuels. La plupart des énoncés E ainsi construits étaient généralement jugés artificiels[note 33], et des énoncés plus conformes à la pratique courante des mathématiciens semblaient ne pas devoir susciter de tels problèmes. Pourtant, vers 1980, Jeff Paris[31] a obtenu des énoncés de forme apparemment naturelle et inoffensive, par exemple affirmant qu'une certaine suite finit par décroître[note 34], mais revenant en fait à définir des entiers si grands que leur « existence » ne peut être prouvée à l'aide des seuls axiomes de Peano ; cela implique que, en n'utilisant que ces axiomes, les énoncés en question sont indécidables.

En 1987, Friedman, Robertson et Seymour ont montré que, si le théorème des mineurs était vrai, le théorème suivant (qui en est un cas particulier[note 35]) serait lui aussi, et pour les mêmes raisons, non démontrable dans des systèmes beaucoup plus forts que l'arithmétique de Peano[32], bien qu'il soit démontrable dans ZFC (et en fait, l'analyse détaillée de la preuve de Robertson et Seymour permet de montrer qu'il est démontrable dans des systèmes nettement moins puissants que ZFC) :

Théorème : Pour tout entier n, il existe un entier m si grand que si G₁, ..., G_m est une suite de graphes finis non orientés, où chaque G_i a au plus n+i sommets et arêtes, alors il existe j < k tels que G_j soit un mineur de G_k.

Là encore, l'entier m est une fonction de n à croissance si rapide[note 36] que les axiomes de Peano (ou même des formes très renforcées de ces axiomes) ne permettent pas de montrer qu'elle est toujours définie, ce qui explique ces résultats d'indécidabilité ; on trouvera dans l'article théorème de Kruskal une description plus précise d'autres théorèmes de logique mathématique analogues, dus eux aussi à Friedman. Ces théorèmes donnent ainsi des exemples de propositions indécidables en arithmétique, considérées comme plus naturelles que celles correspondant au théorème de Gödel[33].

Généralisations : hypergraphes et graphes infinis

En 2011, Robertson et Seymour ont achevé la démonstration d'un résultat analogue sur les hypergraphes[34], définissant un préordre généralisant la relation de mineur, et montrant qu'il s'agit là encore d'un bel ordre. Parmi les conséquences de ce résultat, ils en déduisent que le théorème des mineurs (pour les graphes) s'applique encore si on munit les sommets ou les arêtes d'étiquettes (elles-mêmes ordonnées par un bel ordre), et qu'on demande aux mineurs de respecter l'ordre de ces étiquettes[note 37]. Ce résultat leur a également permis de démontrer une conjecture de Nash-Williams : dans toute suite infinie de graphes, il en existe deux tels que le premier peut être immergé dans le second[note 38].

Il n'est pas impossible qu'un théorème analogue soit encore vrai pour des graphes infinis dénombrables, mais cette conjecture (ou d'ailleurs sa réfutation) est considérée comme encore plus difficile que ne l'est le théorème des mineurs ; Reinhard Diestel pense qu'elle pourrait être liée à une autre conjecture de Seymour, affirmant que tout graphe infini dénombrable possède un mineur (strictement plus petit) qui lui est isomorphe[35]. En revanche, on sait que ces résultats sont faux pour des graphes non dénombrables : Péter Komjáth (en) a démontré que, si $\lambda$ est un cardinal non dénombrable, il existe $2^{\lambda }$ graphes de cardinal $\lambda$ dont aucun n'est un mineur d'un autre[36], et Bogdan Oporowski a obtenu un contre-exemple à la conjecture de Seymour dans le cas non dénombrable[37].

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Robertson–Seymour theorem » (voir la liste des auteurs).

Notes

Il existe d'autres objets mathématiques portant le même nom, par exemple les graphes de fonctions, mais ceux-ci n'ont que peu de rapports avec les graphes étudiés ici.
Plus précisément, comme on le verra plus bas, la formulation de Wagner est que ces graphes ne doivent pas être des mineurs du graphe étudié.
Une expansion d'un graphe est un autre graphe, résultat de l'ajout d'un ou plusieurs sommets sur une ou plusieurs arêtes, ce qui transforme par exemple l'arête •——• en les deux arêtes •—•—•.
Cela revient à dire que les deux graphes K₅ et K_3,3 ne sont pas des mineurs topologiques du graphe considéré.
Contrairement à la forme donnée par Kuratowski ; il existe en effet des suites infinies de graphes deux à deux incomparables pour la relation « H a comme sous-graphe une expansion de G », on en trouvera un exemple dans cet exposé de Bastien Legloannec[PDF](p.10).
Le théorème de Kruskal proprement dit porte sur les arbres étiquetés, et est donc plus général (pour les arbres) que le théorème de Robertson-Seymour ; un théorème couvrant le cas des graphes étiquetés a été démontré en 2011 par Robertson et Seymour, comme mentionné dans la dernière section.
Cette série, intitulée « Graph Minors », contient en fait également quelques articles incidents à la démonstration principale ; d'après R. Diestel, cette dernière correspond aux articles 4 à 7, 9 à 12, et 14 à 20 (Diestel 2005, p. 373) ; de plus, ils ont publié par la suite (à partir de 2009) trois nouveaux articles prolongeant cette démonstration, et intitulés eux aussi Graph Minors (XXI à XXIII).
Un graphe est une forêt s'il est acyclique, autrement dit si c'est un arbre ou une union d'arbres disjoints.
Par la suite, certaines parties de la démonstration ont pu être simplifiées, mais les étapes essentielles demandaient toujours, en 2020, des raisonnements complexes et non constructifs, utilisant en particulier l'axiome du choix ; bien que ce dernier ne soit pas, à proprement parler, strictement nécessaire (voir (en) S. G. Simpson, « Nonprovability of certain combinatorial properties of finite trees », dans Harvey Friedman's Research on Foundations of Mathematics, Elsevier, North-Holland, 1985), cela semble montrer que des simplifications substantielles de la démonstration seront difficiles à obtenir.
Diestel 2005, p. 333 ; il semble que dès le début des années 1990, plusieurs théoriciens des graphes estimaient déjà que leurs efforts seraient couronnés de succès, et commençaient à tirer des conséquences, particulièrement algorithmiques, du futur théorème des mineurs.
On rencontre également fréquemment dans la littérature le terme de mineur topologique, correspondant à des mineurs obtenus uniquement par suppressions d'arêtes et de sommets, et par contraction d'arêtes consécutives, autrement dit, G est un mineur topologique de H s'il existe un sous-graphe de H qui soit une expansion de G ; le théorème de Robertson-Seymour est faux pour cette variante (exposé de Bastien Legloannec, p. 10).
Elle est en effet réflexive (par la suite vide de transformations), et transitive (en composant les suites de transformations) ; de plus, si H est mineur de G et G mineur de H, G et H sont isomorphes.
Diestel 2005, p. 334. Cela revient à dire que, notant ≤ la relation d'ordre, toute suite infinie $\scriptstyle (x_{i})$ d'éléments de l'ensemble contient un couple tel que $\scriptstyle x_{i}\leq x_{j}$ et i < j ; on trouvera une démonstration en français de l'équivalence de cette caractérisation dans cet exposé de Bastien Legloannec [PDF].
On verra plus loin que les ensembles d'obstructions correspondant à une famille fermée sont des antichaînes, or ces ensembles sont le plus souvent très grands, même dans les cas ayant une réelle importance en pratique; ainsi la famille des graphes dont la largeur arborescente vaut au plus k, possède un ensemble d'obstructions d'au moins (k !)² arbres (voir (en) Atsushi Takahashi, Shuichi Ueno et Yoji Kajitani, « Minimal acyclic forbidden minors for the family of graphs with bounded path-width », Discrete Mathematics, vol. 127, n^os 1–3,‎ 1994, p. 293–304, cité par Bruno Courcelle, p.15).
C'est-à-dire que F est telle que tout mineur d'un graphe de F appartienne à F, et alors G est dans F si et seulement si il n'a pour mineur aucun des graphes de S ; voir Diestel 2005, p. 360.
Diestel 2005, p. 334; en réalité, c'est un résultat général sur les beaux ordres, qui n'est au demeurant nullement évident (il demande l'utilisation d'un résultat équivalent au théorème de Ramsey infini) ; dans le cas des graphes, cette forme permet de construire ce qu'on appelle des formes finitaires de Friedman du théorème, obtenant des résultats de logique mathématique qui seront discutés plus loin.
On en trouvera une description informelle dans ce document de Bruno Courcelle [PDF], accompagnée de nombreux exemples d'applications. Robertson et Seymour utilisent en particulier la technique de la décomposition arborescente (qu'ils semblent avoir redécouverte, d'après B. Courcelle) pour obtenir des invariants de graphes essentiels pour leur démonstration.
Il s'agit en fait des composantes « fortement connectées » de ces graphes, c'est-à-dire de celles correspondant à une décomposition arborescente bien choisie (Robertson et Seymour, Graph Minors XVII, Taming a Vortex) ; d'autre part, cette notion de « presque plongeable » cache de redoutables difficultés techniques.
Une description nettement plus rigoureuse est donnée dans Diestel 2005, p. 366 et 367 ; les difficultés techniques correspondant à cette idée sont cependant considérables, et ne sont que mentionnées par R. Diestel.
Cette notion de fermeture est tout à fait générale en mathématiques ; voir l'article Clôture (mathématiques) pour d'autres exemples.
En fait, il s'agit de classes d'équivalence de ces graphes à isomorphisme près ; nous ne ferons désormais plus la distinction.
Chez de nombreux auteurs contemporains, le terme d'« obstruction » en est venu à désigner des objets caractéristiques de l'impossibilité de telle ou telle construction ou raisonnement. Ainsi, la théorie de l'obstruction construit des invariants cohomologiques permettant de déterminer si certains prolongements de fonctions sont ou non possibles.
Robertson, Seymour et Thomas ont montré en 1993 que la famille de Petersen est l'ensemble des obstructions de ces graphes : voir (en) Neil Robertson, P. D. Seymour et Robin Thomas, « Linkless embeddings of graphs in 3-space », Bull. Amer. Math. Soc., vol. 28, n^o 1,‎ 1993, p. 84–89 (MR 1164063, lire en ligne).
On trouvera des listes plus complètes, accompagnées de leurs obstructions (lorsqu'elles sont connues) dans l'article anglais correspondant.
Par analogie avec la théorie des invariants, on appelle invariant d'un graphe un nombre (généralement entier) qui ne dépend pas de certaines transformations que l'on peut faire subir à ce graphe, ou à ses réalisations concrètes comme le tracé du graphe sur une surface. Outre des invariants évidents, comme le nombre de sommets ou d'arêtes (la « taille » du graphe), Robertson et Seymour ont ainsi défini de nombreux invariants liés à ce qu'ils appellent la théorie de la décomposition arborescente des graphes.
Cela suppose que tout mineur d'un graphe pour lequel cet invariant vaut k soit d'invariant $\scriptstyle \leq k$ ; c'est par exemple évident pour les graphes ayant k arêtes, mais c'est faux pour les graphes de nombre chromatique k, parce que contracter une arête peut augmenter le nombre chromatique, comme on le voit sur l'exemple des cycles à 3 et 4 sommets.
Comme on le verra plus loin, l'ensemble des obstructions peut devenir si vaste qu'il est impossible en pratique de l'explorer, ou même de le décrire. Mais de plus, dans le cas général, sa détermination a été démontrée être non calculable, c'est-à-dire ne pouvant être obtenue à l'aide d'une machine de Turing (Fellows et Langston 1994).
On connait par ailleurs les obstructions correspondant à certaines autres familles fermées ; on trouvera un tableau (non exhaustif) de ces résultats dans l'article de la Wikipédia anglophone en:Forbidden graph characterization.
On se reportera à l'article Théorie de la complexité des algorithmes pour des définitions rigoureuses des diverses notions mises en jeu.
Il s'agit de déterminer, étant donné n paires de sommets, s'il existe dans le graphe n chemins disjoints les reliant deux à deux ; le problème reste même NP-complet pour des graphes assez simples, comme cela fut démontré en 2001 par Nishizegi, Vigen et Zhou (en).
À moins de supposer que P=NP, ce qui serait tout à fait remarquable...
Voir l'article problème P=NP pour un exposé plus complet des différents arguments à ce sujet.
Les affirmations initialement construites par Gödel sont des codages du paradoxe du menteur ; bien que d'une forme mathématique acceptable, ces assertions sont d'une complexité redoutable, et ne correspondent à aucun problème qu'un mathématicien jugerait intéressant. On trouvera de nombreuses analyses de ces questions dans la bibliographie de l'article théorèmes d'incomplétude de Gödel.
Il s'agit de suites analogues aux suites de Goodstein, qui commencent par croître pendant un nombre d'étapes démesurément long.
Ce genre de théorème est souvent mentionné sous le nom de « forme finitaire de Friedman » ou, en anglais, FFF pour Friedman finite form ; pour plus de détails, voir cette section de l'article « théorème de Kruskal ».
Voir l'article hiérarchie de croissance rapide pour plus de détails ; dans le cas d'un théorème analogue pour les arbres, Friedman a montré que cette fonction était de l'ordre de f_Γ₀, où Γ₀ est l'ordinal de Feferman-Schütte ; plus explicitement, cet article de Friedman (en) montre comment calculer les premières valeurs d'une fonction de ce genre, où l'on voit, par exemple, qu'on obtient très vite des entiers bien plus grands que le nombre de Graham. Il ne semble pas qu'on ait réussi à déterminer la vitesse de croissance exacte de la fonction m(n), mais l'ordinal correspondant sera de toute façon bien trop grand pour pouvoir être décrit à l'aide des notations usuelles ; se limitant à des arbres et appliquant le théorème de Kruskal, Friedman a montré qu'il était déjà nécessaire d'utiliser le petit ordinal de Veblen ; voir à ce sujet l'article grand ordinal dénombrable, ainsi que (en) Michael Rathjen, The art of ordinal analysis [PDF].
C'est ce théorème qui est à proprement parler la généralisation du théorème de Kruskal pour les arbres mentionné dans l'historique, ce dernier portant sur les arbres étiquetés.
En théorie des graphes, une immersion est une injection telle que les arêtes du premier graphe correspondent à des chemins disjoints du second.

Références

Casimir Kuratowski, « Sur le problème des courbes gauches en Topologie », Fundam. Math., vol. 15,‎ 1930, p. 271–283 (lire en ligne [PDF]) ; la démonstration de Kuratowski n'est pas énoncée dans le langage de la théorie des graphes, mais peut aisément s'y ramener.
(de) K. Wagner, « Über eine Eigcenschaft der ebenen Komplex », Math. Ann., vol. 114,‎ 1937, p. 570–590 (lire en ligne).
(en) Béla Bollobás, Modern Graph theory, Springer-Verlag, 1998, pp. 24 et 25.
Diestel 2005, p. 373.
(en) J. B. Kruskal, « Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture », Transactions of the American Mathematical Society, American Mathematical Society, vol. 95, n^o 2,‎ mai 1960, p. 210–225
Diestel 2005, p. 335–336 ; Lovász 2005, section 3.3, p. 78–79.
Robertson et Seymour 1983
Notice de l'AMS pour le prix Fulkerson 2006 (en) [PDF]
On le trouve cependant encore parfois mentionné sous le nom de « théorème des mineurs », par exemple dans Bienstock et Langston 1995.
Voir par exemple Delahaye 2008, et Diestel 2005, p. 326 et p. 355, ainsi que la notice de l'AMS pour le prix Fulkerson 2006.
Lovász 2005 (p.2 du document en ligne)
Voir par exemple Diestel 2005, p. 334, section 12.1, "well-quasi-ordering", ainsi que N. Bourbaki, Éléments de mathématique – Théorie des ensembles, ch. III, § 1, n° 2, p. 3, pour les définitions et les premières propriétés des ordres partiels et des préordres.
Lovász 2005, p. 78.
Diestel 2005, p. 334, proposition 12.1.1.
Robertson et Seymour 2004
Diestel 2005, p. 365.
Diestel 2005, p. 333
Diestel 2005, p. 365 et suivantes
Bienstock et Langston 1995, corollaire 2.1.1; Lovász 2005, théorème 4, p. 78.
Diestel 2005, p. 360.
Lovász 2005, p. 76–77.
En 2018, une recherche systématique a obtenu 17 535 obstructions, et un argument heuristique montre qu’il n’y en aurait au plus qu’une ou deux autres ; voir (en) Wendy Myrvold et Jennifer Woodcock, A large set of torus obstructions and how they were discovered, 2018 (lire en ligne).
(en) Bojan Mohar et Carsten Thomassen, Graphs on Surfaces, Hopkins Fulfillment Service, 2001, p. 198.
Bienstock et Langston 1995.
Robertson et Seymour 1995 ; Bienstock et Langston 1995, théorème 2.1.4 et corollaire 2.1.5 ; Lovász 2005, théorème 11, p. 83.
Fellows et Langston 1988 ; Bienstock et Langston 1995, section 6.
Voir, par exemple,(en) W. K. Shih et W. L. Hsu, « A new planarity test », Theoretical Computer Science, vol. 223, n^os 1–2,‎ 1999, p. 179–191 ; on trouvera une analyse plus détaillée de cette question dans l'article Planarity testing de la Wikipédia anglophone.
Voir en ligne le cours de Jeff Erickson, Computational Topology, section 12 (graph minors), p. 3 (en).
Robertson et Seymour 1995
Fellows et Langston 1994.
En collaboration avec divers autres auteurs, tels que L. Harrington ; voir par exemple (en) J. Paris et L. Harrington, A mathematical incompleteness in Peano Arithmetic. dans Handbook for Mathematical Logic (ed. J. Barwise), pp. 1133–1142. Amsterdam, Netherlands: North-Holland, 1977.
Friedman, Robertson et Seymour 1987.
On trouvera des remarques informelles sur cette question dans (en) C. Smorynski, The varieties of arboreal experience, 1982 (lire en ligne), et une analyse plus rigoureuse dans (en) Jean H. Gallier, « What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory », Ann. Pure Appl. Logic, vol. 53, n^o 3,‎ 1991, p. 199–260 (texte intégral sous forme de trois documents PDF : partie 1, partie 2, partie 3).
Robertson et Seymour 2010.
Diestel 2005, p. 367 ; cette conjecture entraîne aisément le théorème des mineurs dans le cas fini.
(en) P. Komjáth, « A note on minors of uncountable graphs », Math. Proc. Camb. Phil. Soc., vol. 117,‎ 1995, p. 7-9
(en) B. Oporowski, « A counterexample to Seymour’s self-minor conjecture », Journal of Graph Theory, vol. 14, n^o 5,‎ 1990 (lire en ligne la première page de l'article.

Bibliographie

Livres

(en) Daniel Bienstock et Michael A. Langston, « Algorithmic implications of the graph minor theorem », dans Network Models, coll. « Handbooks in Operations Research and Management Science » (n^o 7), 1995 (DOI 10.1016/S0927-0507(05)80125-2, lire en ligne [PDF]), p. 481–502.
(en) John Chambers, Hunting for torus obstructions, M.Sc. thesis, Department of Computer Science, UVic, 2002.
(en) Reinhard Diestel, « Minors, Trees, and WQO », dans Graph Theory, Springer, 2005 (lire en ligne [PDF]), p. 326–367.
(en) Harvey Friedman, Neil Robertson et Paul Seymour, « The metamathematics of the graph minor theorem », dans S. Simpson, Logic and Combinatorics, AMS, coll. « Contemporary Mathematics » (n^o 65), 1987, p. 229–261.

Articles scientifiques

Jean-Paul Delahaye, « Une propriété cachée des graphes », Pour la science, vol. avril, n^o 3,‎ 2008, p. 92-97.
Article de vulgarisation.
Bruno Courcelle, « Structuration des graphes et logique », Leçons de mathématiques d'aujourd'hui, vol. 4,‎ 2010, p. 167-194.
Leçon rédigée par Fabrice Bazzaro.
(en) László Lovász, « Graph Minor Theory », Bull. Amer. Math. Soc. (New Series), vol. 43, n^o 1,‎ 2005, p. 75–86 (lire en ligne [PDF]).
(en) Michael R. Fellows et Michael A. Langston, « Nonconstructive tools for proving polynomial-time decidability », Journal of the ACM, vol. 35, n^o 3,‎ 1988, p. 727–739 (DOI 10.1145/44483.44491).
(en) Michael R. Fellows et Michael A. Langston, « On search, decision, and the efficiency of polynomial-time algorithms », Journal of Computer and System Sciences, vol. 49, n^o 3,‎ 1994, p. 769–779.
En voici un résumé étendu [PDF], dû aux auteurs eux-mêmes.
(en) Neil Robertson et Paul Seymour, « Graph Minors. I. Excluding a forest », Journal of Combinatorial Theory, Series B, vol. 35, n^o 1,‎ 1983, p. 39–61 (DOI 10.1016/0095-8956(83)90079-5).
Le premier des vingt articles de la démonstration complète, intitulé Mineurs : exclusion d'une forêt.
En 1995, Reinhard Diestel a publié une preuve simplifiée de ce résultat, dans un article de quatre pages [PDF].
(en) Neil Robertson et Paul Seymour, « Graph Minors. XIII. The disjoint paths problem », Journal of Combinatorial Theory, Series B, vol. 63, n^o 1,‎ 1995, p. 65–110 (DOI 10.1006/jctb.1995.1006).
(en) Neil Robertson et Paul Seymour, « Graph Minors. XX. Wagner's conjecture », Journal of Combinatorial Theory, Series B, vol. 92, n^o 2,‎ 2004, p. 325–357 (lire en ligne [PDF]).
(en) Neil Robertson et Paul Seymour, « Graph Minors. XXIII. Nash-Williams’s immersion conjecture », Journal of Combinatorial Theory, Series B, vol. 100, n^o 2,‎ 2010, p. 181–205 (lire en ligne [PDF]).

Liste complète des vingt-trois articles de Robertson et Seymour

Ces articles (à l'exception de Graph minors. II) sont tous parus dans le Journal of Combinatorial Theory (Series B), mais pas toujours exactement dans l'ordre de leur numérotation (entre parenthèses, une traduction française approximative du titre).

Graph minors. I. Excluding a forest, J. Combin. Theory, Ser. B, 35 (1983), 39–61. (Exclusion d'une forêt)
Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), 309–322. (Aspects algorithmiques de la largeur arborescente)
Graph minors. III. Planar tree-width, J. Combin. Theory, Ser. B, 36 (1984), 49–64. (Largeur arborescente dans le cas planaire)
Graph minors. IV. Tree-width and well-quasi-ordering, J. Combin. Theory, Ser. B, 48 (1990), 227–254. (Bel ordre et largeur arborescente)
Graph minors. V. Excluding a planar graph, J. Combin. Theory, Ser. B, 41 (1986), 92–114. (Exclusion d'un graphe planaire)
Graph minors. VI. Disjoint paths across a disc, J. Combin. Theory, Ser. B, 41 (1986), 115–138. (Chemins disjoints à travers un disque)
Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory, Ser. B, 45 (1988), 212–254. (Chemins disjoints sur une surface)
Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory, Ser. B, 48 (1990), 255–288. (Un théorème de Kuratowski pour des surfaces générales)
Graph minors. IX. Disjoint crossed paths, J. Combin. Theory, Ser. B, 49 (1990), 40–77. (Chemins disjoints croisés)
Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory, Ser. B, 52 (1991), 153–190. (Obstructions à une décomposition arborescente)
Graph minors. XI. Circuits on a surface, J. Combin. Theory, Ser. B, 60 (1994), 72–106. (Circuits sur une surface)
Graph minors. XII. Distance on a surface, J. Combin. Theory, Ser. B, 64 (1995), 240–272. (Distance sur une surface)
Graph minors. XIII. The disjoint paths problem, J. Combin. Theory, Ser. B, 63 (1995), 65–110. (Le problème des chemins disjoints)
Graph minors. XIV. Extending an embedding, J. Combin. Theory, Ser. B, 65 (1995), 23–50. (Extension d'un plongement)
Graph minors. XV. Giant steps, J. Combin. Theory, Ser. B, 68 (1996), 112–148. (Des pas de géant)
Graph minors. XVI. Excluding a non-planar graph, J. Combin. Theory, Ser. B, 89 (2003), 43–76. (Exclusion d'un graphe non planaire)
Graph minors. XVII. Taming a vortex, J. Combin. Theory, Ser. B, 77 (1999), 162–210. (Apprivoiser un sommet)
Graph minors. XVIII. Tree-decompositions and well-quasi-ordering, J. Combin. Theory, Ser. B, 89 (2003), 77–108. (Décomposition arborescente et bel ordre)
Graph minors. XIX. Well-quasi-ordering on a surface, J. Combin. Theory, Ser. B, 90 (2004), 325–385. (Bel ordre sur une surface)
Graph minors. XX. Wagner’s conjecture, J. Combin. Theory, Ser. B, 92 (2004), 325–357. ((en) texte intégral [PDF]) (La conjecture de Wagner)
Graph minors. XXI. Graphs with unique linkages, J. Combin. Theory, Ser. B, 99 (2009), 583–616. ((en) texte intégral [PDF]) (Graphes à liens uniques)
Graph minors. XXII. Irrelevant vertices in linkage problems, J. Combin. Theory, Ser. B, (2011, sous presse). ((en) texte intégral [PDF]) (Sommets n'intervenant pas dans le problème des liens)
Graph minors. XXIII. Nash-Williams’s immersion conjecture, J. Combin. Theory, Ser. B, 100 (2010), 181–205. ((en) texte intégral [PDF]) (La conjecture de plongement de Nash-Williams)

Voir aussi

Liens externes

Sur le « site professionnel de Eric Thierry » (maître de conférences à l'ENS Lyon), on trouvera en particulier un exposé rigoureux de Bastien Legloannec, en français [PDF], contenant des démonstrations complètes des propriétés des beaux ordres (en passant par le théorème de Ramsey infini, qu'il démontre également), une démonstration du théorème de Kruskal dans le cas des arbres non étiquetés, et beaucoup d'exemples et de contre-exemples.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.