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.alt= plan de la ville de Königsberg (à l'époque d'Euler)|180px → alt= le réseau des sept ponts de la ville|179px → alt= le graphe modélisant le problème des ponts|180px 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 pointsIl 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.. Ces modèles sont constitués par la donnée de , appelés des sommets (en référence aux polyèdres), et de 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 dans un graphe donné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é. pour que ce dernier soit planaire. vignette|droite|alt= tracé d'un graphe toroïdal sur un tore|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.
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 (le sens technique exact de cette expression sera détaillé plus loin), il existe une liste finie de graphes 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 ; 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. qu'un graphe était planaire s'il ne contenait pas de sous-graphe qui soit une expansionUne 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 •—•—•. du graphe complet K5, ou du graphe biparti complet K3,3Cela revient à dire que les deux graphes K5 et K3,3 ne sont pas des mineurs topologiques du graphe considéré..
En 1937., Klaus Wagner donnait une forme analogue et d'ailleurs équivalente Béla Bollobás, Modern Graph theory, Springer-Verlag, 1998, pp. 24 et 25. de ce théorème, en caractérisant ces graphes comme ne contenant ni K5 ni K3,3 comme . Cette forme permet une généralisation facile à de nombreuses familles de graphes ayant une propriété analogueContrairement à 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(p.10)., par exemple , 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.).
Un résultat plus faible que cette conjecture, concernant seulement les arbres, découle du théorème de KruskalLe 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., lequel avait été conjecturé en 1937 par Andrew Vázsonyi ; il fut démontré indépendamment en 1960 par Joseph Kruskal. et S. Tarkowski ; , section 3.3, p. 78–79..
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 simplesCette 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 () ; 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). (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êtUn graphe est une forêt s'il est acyclique, autrement dit si c'est un arbre ou une union d'arbres disjoints., le théorème est vrai.), mais introduisant également de nombreux concepts et outils nouveaux, comme la théorie de la décomposition arborescente. L'ensemble de la démonstration couvre au total plus de 500 pagesPar 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 ), cela semble montrer que des simplifications substantielles de la démonstration seront difficiles à obtenir. ; la communauté mathématique en a validé le résultat ; 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., appelé désormais théorème de Robertson-SeymourOn le trouve cependant encore parfois mentionné sous le nom de , par exemple dans ., pour lequel ils reçurent en 2006 le prix FulkersonNotice de l'AMS pour le prix Fulkerson 2006 . ; 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 graphesVoir par exemple , et et p. 355, ainsi que la notice de l'AMS pour le prix Fulkerson 2006..
Le théorème de Robertson-Seymour Définitions préliminaires vignette|alt= 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 (p.2 du document en ligne)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)..
La relation (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èsElle 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. (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éordreVoir par exemple , 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.).
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. Cela revient à dire que, notant ≤ la relation d'ordre, toute suite infinie d'éléments de l'ensemble contient un couple tel que et i < j ; on trouvera une démonstration en français de l'équivalence de cette caractérisation dans cet exposé de Bastien Legloannec . (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