Beaux ordres et graphes Bastien Le Gloannec 21 avril 2009

Voir le pdf : http://perso.ens-lyon.fr/eric.thierry/Graphes2009/bastien...

 

Beaux ordres et graphes Bastien Le Gloannec 21 avril 2009 1 Introduction L’´etude des beaux ordres n’est pas sp´ecifique `a la th´eorie des graphes. Ces ordres apparaissent en effet `a de tr`es nombreuses occasions et l’on peut les voir comme une forme affaiblie des bons ordres. En th´eorie des graphes, l’embl´ematique th´eor`eme des mineurs de Robertson et Seymour a notamment contribu´e `a mettre en avant certaines notions comme les d´ecompositions arborescentes et les beaux ordres. Ces derniers ´etaient toutefois ´etudi´es depuis longtemps, y compris en th´eorie des graphes, ce que nous illustrerons notamment avec le th´eor`eme de Kruskal, qui a lui-mˆeme ´egalement publi´e un survey ayant pour objet la th´eorie des beaux pr´eordres en 1970 ([3]). Nous pr´esenterons dans ce rapport une approche tout d’abord g´en´erale, puis centr´ee sur la th´eorie des graphes, de la notion de bel ordre. Cela nous offrira l’occasion de nous int´eresser finalement au th´eor`eme des mineurs, dont les enjeux et cons´equences ont notamment ´et´e synth´etis´ees dans un survey de Lovasz sur la th´eorie des mineurs ([5]), et de le mettre en relation avec la notion de bel ordre. Enfin, il convient de faire remarquer au lecteur qu’un nombre non n´egligeable de preuves ou exemples de ce rapport sont issus d’exercices (non corrig´es) de [1]. Il n’est par cons´equent pas impossible que des erreurs ou impr´ecisions y figurent malencontreusement. Le lecteur est donc invit´e `a rester vigilant. 2 G´en´eralit´es 2.1 D´efinitions et caract´erisation Commen¸cons par rappeler qu’´etant donn´e un ensemble X quelconque, on appelle pr´eordre sur X toute relation binaire r´eflexive et transitive sur X. Si X est muni d’un pr´eordre, nous parlerons d’anti-chaˆıne pour d´esigner un sous-ensemble de X dans lequel tous les ´el´ements distincts sont deux `a deux incomparables. On appelle beau pr´eordre tout pr´eordre 6 sur X tel que pour toute suite infinie (xn)n∈N d’´el´ements de X, il existe deux indices i < j tels que xi 6 xj . Le couple (xi , xj ) est dans ce cas appel´e bonne paire et toute suite contenant une bonne paire sera appel´ee bonne suite. A l’inverse, une suite qui n’est pas bonne sera ` 1 Beaux ordres et graphes Bastien Le Gloannec dite mauvaise. Ainsi, tout pr´eordre sur X est un beau pr´eordre si et seulement si toute suite infinie de X est bonne. On donne le th´eor`eme de caract´erisation des beaux pr´eordres suivant. Th´eor`eme 1 (Caract´erisation des beaux pr´eordres) Les propositions suivantes sont ´equivalentes : (i) 6 est un beau pr´eordre sur X. (ii) De toute suite infinie d’´el´ements de X, on peut extraire une sous-suite croissante. (iii) X ne contient ni anti-chaˆıne infinie, ni suite infinie strictement d´ecroissante. Bien qu’il soit assez simple de donner une preuve directe de cette caract´erisation, il existe une jolie d´emonstration passant par un th´eor`eme de Ramsey ´enonc´e et d´emontr´e ciapr`es. Mais avant, d´efinissons quelques notations utiles. Etant donn´e un ensemble ´ X, nous noterons Pk(X) l’ensemble des parties finies de X `a exactement k ´el´ements. Pour c > 1, on appelle c-coloration de X toute fonction de X dans {0, . . . , c−1}, qui `a chaque ´el´ement de X associe une couleur parmi c couleurs possibles. Si X est muni d’une c-coloration, on dira qu’un ensemble Y ⊆ X est monocromatique si tous les ´el´ements de Y ont la mˆeme couleur. Th´eor`eme 2 (Ramsey) Soit X un ensemble infini, k > 1, c > 1 et l’on suppose donn´ee une c-coloration de Pk(X). Alors il existe une partie infinie Y ⊆ X telle que Pk(Y ) soit monochromatique. Preuve (Ramsey) On proc`ede par r´ecurrence sur k `a c fix´e. Pour k = 1, quel que soit X infini et une c-coloration de P1(X) (singletons) que l’on assimilera `a une coloration de X, il n’y a qu’un nombre fini de couleurs attribu´ees `a un nombre infini d’´el´ements donc au moins une couleur est affect´ee `a une infinit´e d’´el´ements. Pour k > 1 on suppose que pour tout ensemble Z infini et toute c-coloration de Pk−1(X), il existe une partie infinie Z 0 ⊆ Z telle que Pk−1(Z 0 ) soit monochromatique. Nous allons construire une suite (xn)n∈N d’´el´ements de X ainsi qu’une suite (Xn)n∈N strictement d´ecroissante de parties infinies de X v´erifiant les conditions suivantes (pour tout i) : (i) xi ∈ Xi (ii) Xi+1 ⊆ Xi{xi} (iii) L’ensemble {S∪{xi}, S ∈ Pk−1(Xi{xi})} (i.e. l’ensemble des parties `a k ´el´ements de X contenant xi et dont tous les autres ´el´ements sont pris dans Xi) est monochromatique, et l’on note ci sa couleur. On commence par poser X0 = X et x0 ∈ X quelconque. 2/16 Beaux ordres et graphes Bastien Le Gloannec Supposons construite la suite jusqu’au rang i. On consid`ere l’ensemble Pk−1(Xi{xi}) et l’on d´efinit une c-coloration sur cet ensemble ainsi : pour tout S ∈ Pk−1(Xi{xi}), on pose la couleur de S comme ´etant la couleur de S ∪ {xi} (ensemble `a k ´el´ements car xi ∈/ Xi) dans la c-coloration de Pk(X). Par hypoth`ese de r´ecurrence, il existe Xi+1 ⊆ Xi{xi} ((ii) est v´erifi´ee) tel que Pk−1(Xi+1) soit monochromatique ((iii) est v´erifi´ee) et l’on pose ci la couleur correspondante1 . On choisit alors xi+1 ∈ Xi+1 quelconque ((i) est v´erifi´ee). La suite ´etant maintenant construite, on remarque que la suite des couleurs associ´ees ne prend qu’un nombre fini de valeurs, il en existe donc une extraction ϕ telle que le suite infinie (cϕ(n) )n∈N soit constante, notons C sa valeur. Il ne reste plus qu’`a poser Y = {xϕ(n) , n ∈ N} ⊆ X. Y v´erifie (on a tout fait pour) la propri´et´e attendue : Pk(Y ) est monochromatique. En effet, quel que soit S ∈ Pk(Y ), S est constitu´e d’´el´ements de la suite (xϕ(n) ) et posons xi l’´el´ement de plus petit indice de S. Par construction, S{xi} ∈ Pk−1(Xi+1), et donc, par (iii), S est de couleur ci = C (car xi est issu de le suite extraite (xϕ(n) )) et ce pour tout S, donc Pk(Y ) est monochromatique. D’o`u le r´esultat. On peut maintenant d´emontrer le th´eor`eme de caract´erisation qui nous int´eresse. Preuve (Caract´erisation) Remarquons tout d’abord que les implications (ii) ⇒ (i) et (i) ⇒ (iii) sont ´evidentes. Pour la premi`ere, si pour toute suite il existe une soussuite croissante, alors il existe une infinit´e de bonnes paires et a fortiori la suite est bonne. Pour la seconde, toute suite d’´el´ements distincts d’une anti-chaˆıne infinie, ainsi que toute suite infinie strictement d´ecroissante est une mauvaise suite, ce qui n’existe pas par d´efinition mˆeme d’un beau pr´eordre. Consid´erons maintenant l’implication (iii) ⇒ (i). Soit (xn)n∈N une suite d’´el´ements de X. Consid´erons le graphe infini dont les sommets sont les indices de la suite et les arˆetes les couples (i, j) pour i < j. Pour tous i < j, on colorie l’arˆete (i, j) de la fa¸con suivante : • si xi et xj sont incomparables, on colorie l’arˆete (i, j) en gris. • sinon, si xi 6 xj , i.e. (xi , xj ) est une bonne paire, on colorie l’arˆete (i, j) en vert. • sinon, on a xi > xj et l’on colorie l’arˆete (i, j) en rouge. Par th´eor`eme de Ramsey (pour k = 2 et c = 3 sur les paires d’´el´ements de n, la paire {i, j} avec i < j se voyant attribu´ee la couleur de l’arˆete (i, j) de notre graphe), il existe un sous-graphe infini monochrome. S’il ´etait gris alors on aurait form´e une anti-chaˆıne infinie. S’il ´etait rouge, on aurait trouv´e une sous-suite infinie strictement d´ecroissante. Il ne peut donc qu’ˆetre vert : c’est une sous-suite infinie croissante et donc bonne a fortiori. On notera au passage que par cette mˆeme m´ethode on peut extraire de toute suite de X une sous-suite croissante, i.e. l’implication (i) ⇒ (ii) est d´emontr´ee du mˆeme coup. 3/16 Beaux ordres et graphes Bastien Le Gloannec Dans la suite, nous appellerons bel ordre tout beau pr´eordre qui est en plus un ordre (i.e. anti-sym´etrique). 2.2 Exemples et premi`eres propri´et´es Nous allons exposer ici quelques exemples de beaux pr´eordres et beaux ordres ainsi que quelques propri´et´es simples, naturelles et utiles. Voici tout d’abord quelques remarques imm´ediates sur les beaux pr´eordres. Proposition 1 (Beau pr´eordre induit) Soit 6 est un beau pr´eordre (resp. bel ordre) sur X et Y ⊆ X, le pr´eordre (resp. ordre) induit par 6 sur Y est un beau pr´eordre (resp. bel ordre). Preuve Tout mauvaise suite sur Y muni de l’ordre induit serait aussi une mauvaise suite sur X, or il n’en existe pas par hypoth`ese. Proposition 2 (Ordres et sous-ordres) Soient 61 et 62 sont deux pr´eordres sur X v´erifiant 61⊆62, i.e. ∀x, y ∈ X, x 61 y ⇒ x 62 y. Alors on a 61 beau pr´eordre ⇒ 62 beau pr´eordre mais la r´eciproque est fausse. Preuve Toute bonne suite pour 61 est encore bonne pour 62. Toute suite est donc bonne pour 62 qui est donc un beau pr´eordre. Pour la r´eciproque, comme nous le verrons, la relation de mineur est un bel ordre sur les graphes finis mais pas la relation de mineur topologique. Exemple 1 Les ordres sur N. 1. L’ordre usuel sur N est un bel ordre (car il est total et qu’il n’existe pas de chaˆıne infinie strictement d´ecroissante). 2. L’ordre produit usuel (composante par composante) sur N k est aussi un bel ordre. En effet, de toute suite de N k , on peut extraire une sous-suite croissante ainsi : on extrait une sous-suite croissante (pour l’ordre usuel, bon ordre sur N) suivant la premi`ere composante ; de cette suite on extrait une sous-suite croissante suivant la deuxi`eme composante, et on it`ere ainsi sur toutes les composantes. . . On arrive finalement `a une suite de N k simultan´ement croissante sur toutes les composantes, i.e. croissante pour l’ordre produit. Il est int´eressant de constater qu’`a travers de l’exemple de N k , nous avons donn´e une m´ethode de preuve qui assure imm´ediatement le r´esultat suivant. Proposition 3 (Bel ordre produit) Pour tout n > 1 et tous ensembles X1, . . . , Xn munis respectivement de beaux pr´eordres (resp. beaux ordres) 61, . . . , 6n, le pr´eordre (resp. l’ordre) produit sur X = Qn k=1 Xk, d´efinit par (x1, . . . , xn) 6 (y1, . . . , yn) si et seulement si ∀1 6 k 6 n, xk 6 yk, est un beau pr´eordre (resp. bel ordre) sur X. 4/16 Beaux ordres et graphes Bastien Le Gloannec La preuve est imm´ediate par la m´ethode que nous avons propos´e pour l’exemple 1. Dans la mˆeme veine, ce r´esultat sur le produit cart´esien est ´egalement trivialement valable pour l’union disjointe. Proposition 4 (Bel ordre sur l’union) Pour tout n > 1 et tous ensembles X1, . . . , Xn disjoints munis respectivement de beaux pr´eordres (resp. beaux ordres) 61, . . . , 6n, le pr´eordre (resp. l’ordre) union sur X = Sn k=1 Xk, d´efini par 6= Sn k=1 6k, est un beau pr´eordre (resp. bel ordre) sur X. Exemple 2 Bons ordres et beaux ordres. Une question brˆule certainement les l`evres du lecteur avis´e qui a certainement d´ej`a entendu parler de bons ordres, de relations bien fond´ees et se demande s’il existe un lien avec ces beaux ordres qu’il vient de d´ecouvrir. Une relation bien fond´ee sur un ensemble X est une relation binaire sur X2 telle que tout sous-ensemble non vide de X admette un ´el´ement “minimal” (au sens d’un ´el´ement sans ant´ec´edent par la relation ; en particulier, il n’y a pas n´ecessairement unicit´e de cet ´el´ement). Modulo l’axiome du choix d´ependant, cette d´efinition est ´equivalente `a la non existence de suite infinie d´ecroissante (on dit aussi que la relation est nœuth´erienne en th´eorie de la r´e´ecriture). Ainsi donc un pr´eordre est un beau pr´eordre si et seulement si l’ordre strict associ´e est bien fond´e et qu’il n’existe pas d’anti-chaˆıne infinie. Qu’en est-il des bons ordres ? Un bon ordre sur X est une ordre sur X tel que tout sousensemble non vide de X admette un plus petit ´el´ement (au sens d’un ´el´ement inf´erieur ou ´egal `a tous les autres). En particulier un tel ordre est total. L`a encore, modulo l’axiome du choix d´ependant, cette d´efinition est en fait ´equivalente `a dire que l’ordre est total et la relation d’ordre strict associ´ee est bien fond´ee. Un bon ordre est donc un bel ordre : il n’existe par d’anti-chaˆıne par totalit´e et la relation stricte est bien fond´ee. Ainsi donc tout ensemble bien ordonn´e est ´egalement muni d’un bel ordre. C’´etait par exemple le cas de N pour l’ordre usuel, mais c’est par exemple aussi le cas des N k pour l’ordre lexicographique. Quelques contre-exemples • L’ordre usuel sur Z, Q, R n’est pas un bel ordre (suites infinies strictement d´ecroissantes). • Les ordres produit et lexicographique sur Z k , Qk , R k (suites infinies strictement d´ecroissantes, ou anti-chaˆınes infinies dans le cas de l’ordre produit). • L’inclusion ⊆ sur un ensemble infini : les singletons forment une anti-chaˆıne infinie. 5/16 Beaux ordres et graphes Bastien Le Gloannec 3 Quelques r´esultats 3.1 Lemme de Higman Un r´esultat remarquable est que l’on peut ´etendre tout beau pr´eordre sur X `a l’ensemble X<ω des parties finies de X. On d´efinit en effet la relation 6 sur X<ω ainsi : pour tous A, B ∈ X<ω , A 6 B si et seulement s’il existe une injection f de A dans B telle que pour tout a ∈ A, a 6 f(a). On v´erifie ais´ement que cette relation est un pr´eordre sur X<ω : • R´eflexivit´e : il suffit de prendre f = idA. • Transitivit´e : si A 6 B par une injection f et B 6 C par une injection g, alors ∀a ∈ A, f(a) ∈ B donc g(f(a)) > f(a) > a et g ◦ f compos´ee d’injections reste injective. Dans le cas o`u l’on dispose initialement d’un bel ordre sur X, on obtient ´egalement un bel ordre sur X<ω. En effet, on h´erite de l’anti-sym´etrie : si A 6 B via f et B 6 A via g, alors ∀a ∈ A, g(f(a)) > a. g ◦ f est une bijection de A dans A et cette in´egalit´e exprime le fait que tout ´el´ement de a doive ˆetre envoy´e sur un ´el´ement depuis lequel il est accessible dans le DAG fini (car A fini) de la relation d’ordre (partielle) > sur A. Ainsi, les sources de ce DAG (´el´ements maximaux de A) sont n´ecessairement envoy´ees sur elles-mˆemes. Comme l’application est injective, on ne peut plus r´eutiliser ces sources pour continuer `a construire g ◦ f, on peut donc les retirer du graphe, faisant ainsi apparaˆıtre de nouvelles sources `a leur tour envoy´ees sur elles-mˆemes, et l’on it`ere. . . Finalement, ∀a ∈ A, g(f(a)) = a. Mais a = g(f(a)) > f(a) > a (par B 6 A puis A 6 B) donc f(a) = a et donc A = B. Lemme 1 (Higman – version ensembles) Soit X un ensemble muni d’un beau pr´eordre 6 alors le pr´eordre induit par 6 sur X<ω est un beau pr´eordre. Preuve Par l’absurde, supposons qu’il existe des mauvaises suites sur X<ω. On va construire une suite (Xn)n∈N d’´el´ements de X<ω par r´ecurrence. Supposons construite la suite jusqu’au rang i et supposons qu’elle v´erifie l’hypoth`ese suivante : X0, . . . , Xi est le d´ebut d’au moins une mauvaise suite sur X<ω. On alors choisit Xi+1 ∈ X<ω de cardinal minimal tel que X0, . . . , Xi , Xi+1 soit le d´ebut d’une mauvaise suite. La suite ainsi form´ee est bien sˆur une mauvaise suite (sinon il existe i < j tels que Xi 6 Xj et donc X0, . . . , Xi , . . . , Xj ne saurait ˆetre le d´ebut d’une mauvaise suite). A fortiori, on a donc ∀n ∈ N, Xn 6= ∅ (en remarquant que ∀A ∈ X<ω , ∅ 6 A). Pour tout n, on peut donc choisir xn ∈ Xn quelconque et poser Yn = Xn{an}. Par caract´erisation (iii) dans X muni d’un bel ordre, la suite (xn)n∈N admet une sous-suite (xϕ(n) )n∈N croissante. Par minimalit´e du cardinal dans le choix Aϕ(0), la suite X0, . . . , Xϕ(0)−1 , Yϕ(0), Yϕ(1), Yϕ(2), . . . est bonne et contient donc une bonne paire. Une telle paire ne peut ˆetre ni de la forme (Xi , Xj ) (puisque (Xn)n∈N est mauvaise) ni (Xi , Yj ) puisque Xj > Yj (et on aurait Xi 6 Yj < Xj ). Une bonne paire est donc de la forme (Yi , Yj ) et donc Yi 6 Yj via une 6/16 Beaux ordres et graphes Bastien Le Gloannec injection f de Yi vers Yj . On prolonge alors f en f 0 de Xi vers Xj en posant f 0 (xi) = xj (on a bien xj > xi car xi et xj sont issus de la suite (xϕ(n) )n∈N) on a construit une injection assurant que Xi 6 Xj , ce qui est absurde car la suite (Xn)n∈N est mauvaise. La r´eciproque du lemme de Higman est ´egalement vraie : il suffit de consid´erer les singletons. Il existe ´egalement une version mots du lemme de Higman que nous allons maintenant consid´erer. Si Σ un alphabet muni d’un beau pr´eordre 6, on peut ´etendre ce pr´eordre `a Σ∗ en posant, pour tous mots u = u1 . . . up et v = v1 . . . vq, u 6 v si et seulement si il existe une injection f de {1, . . . , p} dans {1, . . . , q} telle que pour tout 1 6 i 6 p, ui 6 vf(i) . Lemme 2 (Higman – version mots) Si Σ un alphabet muni d’un beau pr´eordre 6, alors le pr´eordre induit par 6 sur Σ ∗ est beau pr´eordre. Ce r´esultat pourrait se d´emontrer par une preuve totalement analogue `a la pr´ec´edente. Nous allons plutˆot proc´eder en r´eutilisant le r´esultat pr´ec´edent. Nous allons mˆeme montrer un peu plus : l’´equivalence des deux versions du lemme de Higman. Preuve (´equivalence des versions ensembles/mots) Il suffit de remarquer que pour toute permutation σ de {1, . . . , p} et toute permutation σ 0 de {1, . . . , q}, si l’on pose u 0 = uσ(1) . . . uσ(p) et v 0 = vσ0(1) . . . vσ0(q) alors si l’on a u 6 v via une injection f, on a ´egalement u 0 6 v 0 via l’injection σ 0−1 ◦ f ◦ σ. En d’autres termes, l’ordre des lettres n’a aucune importance, on peut les voir comme des ensembles finis de lettres, i.e. des ´el´ements de Σ∗<ω. L’´equivalence des ´enonc´es est alors imm´ediate. Il est `a noter que l’ordre des lettres n’´etant pas important, pour tout mot u et toute permutation u 0 de u, u 0 6= u, on aura tout de mˆeme u 6 u 0 et u 0 6 u sans avoir u = u 0 : l’anti-sym´etrie n’est pas v´erifi´ee, on ne peut avoir qu’un pr´eordre ici et pas d’ordre. Enfin, il existe en combinatoire sur les mots une autre version usuelle du lemme de Higman. On utilise pour cette derni`ere l’ordre suivant : u 6 v si et seulement si u est un sous-mot de v (au sens d’une suite extraite, aux lettres non n´ecessairement cons´ecutives dans v). On v´erifie ais´ement que cette relation sur les mots est cette fois un ordre et pas seulement un pr´eordre. Lemme 3 (Higman – version sous-mots) La relation de sous-mot 6 est un bel ordre sur Σ ∗ . Cela revient `a prendre l’´egalit´e comme relation et `a imposer de plus `a l’injection d’ˆetre croissante dans la version mots du lemme de Higman. On peut en fait montrer que le lemme de Higman est encore vrai si l’on impose `a l’injection d’ˆetre croissante. Il implique alors directement la version sous-mots (que l’on pourrait aussi d´emontrer directement en adaptant la preuve du th´eor`eme de Higman en une preuve plus simple par certains aspects, puisque l’on ne dispose plus d’un beau pr´eordre sur Σ, mais en assurant la croissance de l’injection). 7/16 Beaux ordres et graphes Bastien Le Gloannec 3.2 Th´eor`eme de Kruskal Dans cette section, nous allons ´etudier le th´eor`eme de Kruskal sur la classe des arbres finis. Avant toute chose, une remarque pr´eliminaire et importante pour toute la suite s’impose : les relations de mineur (not´ee 4) et mineur topologique sont des relations d’ordre (partielles) sur la classe des graphes finis. Ce fait est tr`es simple `a v´erifier. Th´eor`eme 3 (Kruskal, [2]) La relation de mineur topologique est un bel ordre sur les arbres finis. Il est `a noter que ce r´esultat ne restera cependant pas vrai sur la classe des graphes finis quelconques toute enti`ere comme nous allons le voir dans la section suivante. Afin de d´emontrer ce th´eor`eme, nous allons renforcer la notion de mineur topologique en d´efinissant la notion de mineur topologique enracin´e sur la classe des arbres. Rappelons si n´ecessaire les d´efinitions de la notions de mineur topologique. On dit qu’un graphe H est une subdivision d’un graphe G si H peut ˆetre obtenu `a partir de G en “subdivisant” des arˆetes, i.e. en rempla¸cant une arˆete de G par une chaˆıne de longueur arbitraire. On dit alors qu’un graphe G est un mineur topologique d’un graphe H s’il existe un sous-graphe H0 de H tel que H0 soit une subdivision de G. En d’autres termes, G est obtenu `a partir de H en supprimant des arˆetes, des sommets, et en contractant des chaˆınes. Etant donn´es ´ deux arbres enracin´es T et T 0 , de racines respectives r et r 0 (rappelons que l’enracinement induit un ordre naturel sur l’arbre), on dira que T 6 T 0 si et seulement s’il existe une isomorphisme ϕ d’une subdivision T0 de T (pour la mˆeme racine, ce qui induit un ordre sur T0) vers un sous-arbre T1 de T 0 qui pr´eserve l’ordre, i.e. telle que si x < y dans T alors ϕ(x) < ϕ(y) dans T1 ⊆ T 0 . Il est ais´e de v´erifier que l’on d´efinit bien un pr´eordre sur les arbres enracin´es ainsi. Essentiellement, la relation d´efinie est en tout points similaire `a la notion de mineur topologique, si ce n’est qu’elle pr´eserve l’orientation pour des arbres enracin´es. La Fig. 1 illustre cette notion. La m´ethode de preuve qui suit est totalement similaire `a celle mise en œuvre pour d´emontrer le lemme de Higman. D’ailleurs, nous n’h´esiterons pas `a renvoyer par endroit le lecteur `a cette derni`ere dans la preuve qui suit. Preuve (Kruskal, m´ethode de Nash-Williams, [6]) Nous allons d´emontrer que la relation de mineur topologique enracin´e est un beau pr´eordre sur les arbres finis enracin´es, ce qui implique naturellement ce que l’on veut d´emontrer du fait de l’´equivalence suivante : T 0 est un mineur topologique de T si et seulement si il existe un enracinement de T et un enracinement de T 0 tels que T 0 soit un mineur topologique enracin´e de T pour ces enracinements. Par l’absurde (i.e. on suppose l’existence de mauvaises suites), on proc`ede comme dans la preuve du lemme de Higman (s’y reporter si n´ecessaire) en construisant une suite (Tn)n∈N d’arbres enracin´es (de racines respectives les ´el´ements de la suite (rn)n∈N) en choisissant `a chaque ´etape i un plus petit arbre (en nombre de sommets) Ti de racine ri 8/16 Beaux ordres et graphes Bastien Le Gloannec Fig. 1 – Mineur topologique enracin´e, [1] tel que T0, . . . , Ti soit le d´ebut d’une mauvaise suite. L`a encore, (Tn)n∈N est une mauvaise suite. Pour tout i ∈ N, on pose Si l’ensemble des composantes connexes du graphe Ti dont on a retir´e la racine ri , chacune de ces composantes ´etant enracin´ee en le voisin de ri dans la composante, de sorte que l’ordre induit par l’enracinement reste exactement le mˆeme que dans Ti . On pose S = S n∈N Sn. Montrons alors que l’on a un beau pr´eordre sur S. Soit (tn)n∈N une suite quelconque de S en prenant, pour tout n, tn ∈ Sin . Soit m tel que im soit minimal parmi les in. D`es lors, la suite T0, . . . , Tim−1, tm, tm+1, tm+2, . . . est bonne (car tm ∈ Sim est une composante connexe issue de la suppression de rim dans Tim et a au moins un sommet de moins que Tim) et contient donc une bonne paire qui ne peut ˆetre que de la forme (ti , tj ) avec i < j. En effet, comme (Tn) est mauvaise, cela ne peut ˆetre (Ti , Tj ) et si c’´etait (Ti , tj ), alors Ti 6 tj < Tij avec i 6 im − 1 et par choix de m on a ij > im donc i < ij ce qui contredirait le fait que (Tn) soit mauvaise. On a donc trouv´e en (ti , tj ) une bonne paire dans la suite (tn) (a priori quelconque) de S qui est donc bien muni d’un beau pr´eordre. Puisque chaque Sn est une partie finie de S muni d’un beau pr´eordre, alors par lemme de Higman la suite (Sn) est bonne et admet donc une bonne paire (Si , Sj ), i < j, et donc Si 6 Sj via une injection f de Si dans Sj v´erifiant, pour tout t ∈ Si , t 6 f(t) via un certain isomorphisme ϕt . On pose ϕ le morphisme r´ealisant l’union de sous ces ϕt et on le prolonge `a Ti en posant ϕ(ri) = rj . L’ordre est ainsi pr´eserv´e (car on avait d´ej`a remarqu´e que l’ordre restait inchang´e dans les composantes connexes lorsque l’on effectuait la suppression de ri) et ϕ d´efinit naturellement un isomorphisme assurant Ti 6 Tj : on a trouv´e une bonne paire dans la mauvaise s´equence (Tn), d’o`u la 9/16 Beaux ordres et graphes Bastien Le Gloannec contradiction. 3.3 Contre-exemples On consid`ere dans cette section deux contre-exemples instructifs. Le premier montre que le th´eor`eme de Kruskal ne tient plus si l’on restreint la relation `a celle de sous-graphe connexe, et le second que le th´eor`eme des mineurs ne reste pas non plus vrai si l’on se limite `a la relation de mineur topologique. Contre-exemple 1 La relation de sous-graphe connexe n’est pas un bel ordre pour la classe des arbres finis. Notons que les propri´et´es de r´eflexivit´e, de transitivit´e et d’anti-sym´etrie sont trivialement v´erifi´ees pour cette relation. Remarquons ´egalement qu’un graphe n’a qu’un nombre fini de sous-graphes connexes (et ils sont tous de taille inf´erieure ou ´egale), par cons´equent il est inutile d’esp´erer obtenir une suite strictement d´ecroissante ici. Nous allons maintenant exhiber une anti-chaˆıne infinie de d’arbres. La Fig. 2 pr´esente une telle famille d’arbres deux `a deux incomparables pour la relation de sous graphe connexe. (a) T1 (b) T2 (c) T3 n arˆetes (d) Tn Fig. 2 – Anti-chaˆıne infinie pour la relation de sous-graphe connexe sur les arbres finis Contre exemple 2 La relation de mineur topologique n’est pas un bel ordre sur la classe des graphes finis. Rappelons que ce qui ´etait vrai sur la classe des arbres finis ne l’est donc plus lorsque l’on passe aux graphes quelconques. Mais cela sera par contre vrai sur la classe des graphes fini en ´elargissant la relation aux mineurs. L`a encore, comme dans l’exemple pr´ec´edent, il est inutile d’esp´erer obtenir une suite infinie strictement d´ecroissante, un graphe n’ayant qu’un nombre fini de mineurs topologiques. On cherche donc une anti-chaˆıne infinie, ce qui 10/16 Beaux ordres et graphes Bastien Le Gloannec est moins ´evident `a obtenir que dans le cas pr´ec´edent. L’id´ee est que pour montrer qu’un graphe H est un mineur topologique d’un graphe G, on peut exhiber un isomorphisme de graphe d’une subdivision de H vers une sous-graphe de G. Il n’est pas difficile de remarquer que ce morphisme envoie n´ecessairement tout sommet de H vers un sommet de degr´e sup´erieur ou ´egal dans G. Organiser judicieusement les degr´es est un moyen de forcer tel sommet `a ˆetre envoy´e sur tel autre sommet, en agen¸cant les sommets entre-eux de fa¸con `a ce qu’il ne soit pas possible qu’un graphe soit le mineur d’un autre (ici il y a 2 sommets de degr´es 6 par graphe qui sont forc´ement envoy´es les uns sur les autres, la chaine les s´eparant n’´etant pas bien contractable) on construit une anti-chaˆıne infinie d´ecrite sur la Fig. 3, et bas´ee sur une adaptation naturelle de l’exemple pr´ec´edent. (a) T1 (b) T2 (c) T3 n blocs (d) Tn Fig. 3 – Anti-chaˆıne infinie pour la relation de mineur topologique sur les graphes quelconques 4 Autour du th´eor`eme des mineurs Dans cette section, nous allons nous int´eresser au fameux th´eor`eme des mineurs et voir en quoi il est fondamentalement li´e `a la notion de bel ordre. Mais avant, pr´ecisons que nous dirons dans tout ce qui suit qu’une classe de graphes C est ferm´ee par mineurs si et seulement si tout mineur d’un graphe de C est encore dans C, i.e. la classe est stable par passage `a un mineur. 4.1 Approche et ´enonc´e Un r´esultat bien connu en th´eorie des graphes est que l’on peut caract´eriser la classe des graphes planaires comme l’ensemble des graphes n’admettant ni K5 ni K3,3 comme mineur. Ce r´esultat de 1930 est connu sous le nom de th´eor`eme de Kuratowski. 11/16 Beaux ordres et graphes Bastien Le Gloannec Th´eor`eme 4 (Kuratowski, [4]) Un graphe est planaire si et seulement s’il n’admet ni K5 ni K3,3 comme mineur. Ce r´esultat a particuli`erement marqu´e les th´eoriciens des graphes qui en ont longtemps cherch´e des g´en´eralisations. Il est en effet tr`es commode de disposer d’une telle caract´erisation par une famille finie de mineurs interdits : d’une part on peut montrer la non appartenance `a la classe d’un graphe en donnant pour certificat une s´equence de transformations conduisant au mineur interdit et d’autre part l’on peut tester l’appartenance `a la classe en temps polynomial. Malheureusement, encore auourd’hui bien peu de r´esultats explicites de ce genre sont connus et le th´eor`eme de Kuratowski reste de loin le plus embl´ematique. Toutefois, Wagner aurait conjectur´e d`es 1970 que toute classe de graphes ferm´ee par mineurs (i.e. telle que tout mineur d’un graphe de la classe est encore dedans) pouvait ˆetre caract´eris´ee par une famille finie de mineurs interdits, `a la mani`ere du th´eor`eme de Kuratowski. Ce r´esultat a ´et´e finalement ´et´e d´emontr´e par Robertson et Seymour `a travers une s´erie de vingts articles publi´es entre 1983 ([8]) et 2004 ([10]). Th´eor`eme 5 (Robertson & Seymour, [10]) Toute classe de graphes ferm´ee par mineurs peut ˆetre caract´eris´ee par une famille finie de mineurs interdits. Pour bien comprendre les enjeux de ce th´eor`eme, il est a noter que c’est bel et bien l’aspect fini de la famille de mineurs qui en est l’´el´ement important. Ce mˆeme r´esultat pour une famille infinie est une propri´et´e basique et bien connue ´enonc´e ci-dessous. Introduisons tout d’abord une notation utile. Pour K un ensemble de graphes, on d´efinit la classe Forb4(K) comme l’ensemble des graphes n’admettant aucun des ´el´ements de K comme mineur, i.e. la classe de graphes caract´eris´ee par un ensemble de mineurs interdits K. On rappelle que l’on note 4 la relation de mineur (et ≺ la relation stricte associ´ee). Inversement, pour tout classe C, on appelle ensemble de Kuratowski de C l’ensemble KC = {G graphe/G /∈ C et ∀H ≺ G, H ∈ C} i.e. l’ensemble des ´el´ements minimaux pour 4 dans le compl´ementaire C de C. Par construction mˆeme, les ´el´ements de KC forment une anti-chaˆıne pour 4. Proposition 5 Une classe de graphes est ferm´ee par mineurs si et seulement si on peut la caract´eriser par une famille (´eventuellement infinie) de mineurs interdits, auquel cas KC est une famille qui convient et c’est la famille minimale pour l’inclusion unique `a convenir. Preuve Si C est une classe de graphes ferm´ee par mineurs, il suffit de remarquer que C = Forb4(C) (pour C le compl´ementaire de la classe). Par ailleurs, KC est incluse dans toute autre famille K `a convenir car si un ´el´ement G de KC n’y ´etais pas, alors il serait interdit (car il doit l’ˆetre) en faisant intervenir un ´el´ement de K qui serait un mineur strict de G. Or par d´efinition mˆeme de KC, tout mineur strict de ses ´el´ements est dans C. D’o`u 12/16 Beaux ordres et graphes Bastien Le Gloannec la contradiction et donc KC ⊆ K. Par ailleurs KC convient ´egalement car s’il existait un ´el´ement G de C non interdit par KC, alors aucun de ses mineurs ne serait dans KC. Imaginons l’arbre des mineurs de G sur lequel G est la racine, suivent tous les mineurs stricts directs (issus d’une op´eration), puis les mineurs stricts directs des mineurs,etc (on autorise les r´ep´etitions de sommets correspondant `a un mˆeme graphe). Toutes les feuilles de l’arbre correspondent au graphe `a un sommet qui appartient ´evidemment `a tout classe de graphes ferm´ee par mineurs (suppos´ee implicitement non vide). Mais alors il existe dans le graphe des sommets appartenant `a C (ainsi qu’au moins la racine appartenant `a C). Par stabilit´e par mineurs de C, ces sommets ont tous leurs descendants dans C. Consid´erons un sommet S de profondeur maximale dans l’arbre parmi ceux correspondant `a un graphe de C. Tous ses descendants sont donc dans C. Ce sommet est donc dans KC et est un mineur de G. D’o`u la contradiction. R´eciproquement, tout Forb4(K) est trivialement ferm´e par mineurs. 4.2 Mineurs et beaux ordres Le th´eor`eme des mineurs a une autre formulation mettant plus en valeur ce qui nous pr´eoccupe, `a savoir les beaux ordres. Th´eor`eme 6 (des mineurs – deuxi`eme version) La relation de mineur est un bel ordre sur la classe des graphes finis. Il est int´eressant de montrer l’´equivalence des deux ´enonc´es de ce th´eor`eme. Preuve (´equivalence des ´enonc´es) Comme nous l’avons d´ej`a vu, si une classe C est ferm´ee par mineurs, alors C = Forb4(KC) o`u KC est une anti-chaˆıne pour 4. Mais alors, si KC n’est pas fini, alors on a trouv´e une anti-chaˆıne infinie et donc 4 ne saurait ˆetre un bel ordre sur la classe des graphes finis. On a montr´e par contrapos´ee que la deuxi`eme version implique la premi`ere (qui est clairement ´equivalente `a la finitude de KC en utilisant la proposition 5). R´eciproquement, supposons un instant par l’absurde qu’il existe une anti-chaˆıne infinie K. La classe C = Forb4(K) est close par mineurs et admet donc un ensemble de Kuratowski KC fini tel que C = Forb4(KC). Mais alors, KC est un ensemble de mineurs qui interdit l’ensemble des ´el´ements K. Et surtout, par proposition 5, KC ⊆ K. Il y a donc dans K infini une infinit´e d’´el´ements `a ne pas ˆetre dans KC et `a pourtant admettre pour mineur un ´el´ement de KC et donc de K, qui ne saurait donc ˆetre une anti-chaˆıne. D’o`u le r´esultat. 4.3 Aspects algorithmiques Le th´eor`eme suivant constitue une cons´equence algorithmique non n´egligeable du th´eor`eme des mineurs. 13/16 Beaux ordres et graphes Bastien Le Gloannec Th´eor`eme 7 L’appartenance d’un graphe `a une classe de ferm´ees par mineurs peut toujours ˆetre test´ee en temps polynomial. Ce r´esultat tr`es fort et g´en´eral repose sur une m´ethode algorithmique en O(n 3 ) (Seymour & Robertson, [9]). Toutefois la constante est ´enorme et d´epend fortement de la liste des mineurs exclus. Nous n’entrerons cependant pas dans les d´etails algorithmiques ici. 4.4 Une conjecture plus forte Dans les ann´ees 1980, Seymour a conjectur´e l’´enonc´e suivant. Conjecture 1 (Seymour) Tout graphe infini d´enombrable est un mineur strict de luimˆeme. Pr´ecisons le sens `a donner `a la notion de mineur strict ici : G infini est un mineur strict de lui mˆeme s’il existe une s´equence de transformations, parmi les suppressions de sommets, d’arˆetes et les contractions d’arˆetes, non vide et finie telle que le graphe obtenu soit isomorphe `a G. Cela peut sembler ´etonnant de prime abord, puisque l’on s’int´eresse ici `a des graphes infinis d´enombrables (un contre-exemple ind´enombrable a ´et´e d´ecouvert en 1990 par Oporowski, [7]), mais ce r´esultat impliquerait le th´eor`eme des mineurs. Preuve (le th´eor`eme des mineurs est un corollaire de la conjecture) Pour la classe des graphes connexes Par l’absurde, supposons la conjecture v´erifi´ee mais pas le th´eor`eme des mineurs. Comme nous l’avons d´ej`a vu, il n’y a jamais de suite infinie strictement d´ecroissante pour la relation 4. Par cons´equent, c’est qu’il existe une anti-chaˆıne infinie de graphes finis {G0, G1, . . .} (d´enombrable car l’ensemble des graphes finis est lui-mˆeme d´enombrable). Posons alors G = S i∈N Gi (sans cr´eer d’arˆetes entre-eux). G est un mineur strict de lui-mˆeme donc il existe une s´equence non vide de transformations qui produisent finalement un graphe G0 isomorphe `a G. Comme il y a au moins une transformation, au moins un graphe Gi est modifi´e. Mais Gi ne peut avoir ´et´e supprim´e compl`etement. En effet, s’il l’avait ´et´e, alors comme il est pr´esent dans G’, et qu’il est connexe, c’est qu’il a ´et´e obtenu `a partir d’un autre graphe (et d’un seul car on est dans le cas connexe) de l’anti-chaˆıne, graphe dont il serait donc mineur, ce qui est impossible par hypoth`ese. Mais alors il a ´et´e r´eduit sans totalement disparaˆıtre. Chaque composante connexe d’apr`es r´eduction (et il y en a au moins une) ´etant isomorphe `a un graphe de l’anti-chaˆıne, graphe qui est donc un mineur de G, ce qui est absurde. D’o`u le r´esultat dans le cas connexe. 14/16 Beaux ordres et graphes Bastien Le Gloannec Et dans le cas g´en´eral On peut voir un graphe fini quelconque comme l’ensemble de ses composantes connexes, i.e. comme une partie finie de la classe des graphes connexes. Il n’est pas difficile alors de remarquer que l’on a H 4 G avec H et G non n´ecessairement connexes si et seulement si G a au moins autant de composantes connexes que H et il existe une injection de H vers G envoyant chaque composante connexe c 0 de H vers une composante c de G telle que c 0 4 c, autrement dit c 0 4 f(c 0 ) (on r´eduit alors G en H en supprimant toutes les composantes qui n’appartiennent pas `a l’image de f, et en r´eduisant chaque f(c 0 ) en la composante c 0 de H). La relation de mineur sur les graphes finis est donc exactement la relation induite par la relation de mineur pour la classe graphes connexes (qui est un bel ordre) sur l’ensemble de ses parties finies. Par lemme de Higman, on en d´eduit que la relation 4 est un bel ordre sur la classe des graphes quelconques. 5 Conclusion L’´etude des beaux ordres a permis d’´etablir un certain nombre de th´eor`emes int´eressants, notamment, pour ce qui est de l’informatique fondamentale, en combinatoire sur les mots et en th´eorie des graphes comme nous avons pu l’illustrer tout au long de ce rapport. Le th´eor`eme des mineurs de Robertson et Seymour, qui est probablement le plus gros r´esultat de la th´eorie des graphes en l’´etat actuel de l’art, se ram`ene ainsi `a d´emontrer que la relation de mineur est un bel ordre sur la classe des graphes finis. Sur des structures combinatoires peu contraintes comme les graphes ou les mots, les beaux ordres peuvent ˆetre vus comme une alternative faible `a des notions plus fortes telles que les bons ordres, omnipr´esents en th´eorie des ensembles. C’est finalement un moyen fructueux de ramener des probl`emes combinatoires `a des objets math´ematiques bien connus et ´etudi´es. R´ef´erences [1] R. Diestel. Graph theory. Springer, 2005. [2] JB Kruskal. Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society, pages 210–225, 1960. [3] J.B. Kruskal. The theory of well-quasi-ordering : A frequently discovered concept. J. Combinatorial Theory Ser. A, 13(3) :297–305, 1972. [4] K. Kuratowski. Sur le probleme des courbes gauches en topologie. Fund. Math, 15(27) :1–283, 1930. [5] L. Lov´asz. Graph minor theory. Bulletin-American Mathematical Society, 43(1) :75, 2006. [6] C. Nash-Williams. On well-quasi-ordering finite trees. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 59, 1963. 15/16 Beaux ordres et graphes Bastien Le Gloannec [7] B. Oporowski. A counterexample to Seymour’s self-minor conjecture. Journal of Graph Theory, 14(5), 1990. [8] Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest. J. Comb. Theory, Ser. B, 35(1) :39–61, 1983. [9] Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1) :65–110, 1995. [10] Neil Robertson and Paul D. Seymour. Graph minors. xx. wagner’s conjecture. J. Comb. Theory, Ser. B, 92(2) :325–357, 2004. 16/16