Beaux ordres et graphes.

Un bel ordre (X,≤) est une relation d'ordre ≤ sur X (càd. réflexive, antisymétrique et transitive) telle que, de toute suite infinie x₀, x₁, x₂, .... d'éléments de X, on peut extraire deux indices i<j tels que x_i≤x_j.

Un certain nombre d'ensembles infinis en mathématiques discrètes s'avèrent être muni d'un bel ordre intéressant, qui induit d'importantes conséquences tant du point de vue mathématique que du point de vue algorithmique. C'est le cas d'un des plus gros théorèmes de théorie des graphes : le théorème des mineurs, de N. Robertson et P. Seymour (ex-conjecture de Wagner). L'objectif de ce sujet est d'illustrer ce propos par des exemples et éventuellement des contre-exemples.  Les trois théorèmes ci-dessous sont très représentatifs :

• Lemme de Higman (version ensembles, preuve abordable) : Soit X un ensemble muni d'un bel ordre ≤, et X^<ω l'ensemble des parties finies sur X muni de la relation A ≤ B s'il existe une injection f de A dans B telle que ∀ a ∈ A, a ≤ f(a). Alors cette relation ≤ est un bel ordre sur X^<ω.
• Théorème de Kruskal (preuve abordable) : La relation de mineur topologique est un bel ordre sur les arbres finis.
• Théorème des mineurs de Robertson et Seymour (> 600 pages de preuves !) : La relation de mineur est un bel ordre sur les graphes finis.
  

Les questions ci-dessous peuvent vous guider :

1. Donner quelques précisions sur la notion de bel ordre. En particulier il existe d'autres caractérisations, par exemple :
   
• ordre tel que de toute suite infinie, on peut extraire une sous-suite croissante,
  
• ordre ne contenant ni antichaîne infinie, ni suite infinie strictement décroissante.
2. Donner des exemples et des contre-exemples simples de beaux ordres. Par exemple est-ce que N^k muni de l'ordre produit classique (ordre composante par composante) est un bel ordre ?
3. Présenter les trois théorèmes cités, avec éventuellement des preuves (sauf Robertson et Seymour, à moins d'une idée fulgurante !).
4. Le lemme de Higman existe aussi en version mots : soit Σ un alphabet muni d'un bel ordre ≤, on peut l'étendre en une relation sur Σ^* (mots finis) où pour deux mots u=u₁...u_p et v=v₁...v_q, on a u ≤ v s'il existe f injection de {1,...,p} dans {1,...,q} telle que ∀ i, u_i ≤ v_f(i), alors cette relation est un bel ordre sur Σ^*. Montrer qu'on peut déduire rapidement la version ensembles de la version mots, et inversement.
5. Qu'est-ce qui fait dire qu'une classe de graphes finis est close par mineur si et seulement elle peut se définir par une famille finie de mineurs interdits ?
6. Montrer que la relation de sous-graphe connexe n'est pas un bel ordre sur la classe des arbres finis.
7. Montrer que la relation de mineur topologique n'est pas un bel ordre sur la classe des graphes finis.
8. Seymour a conjecturé que "tout graphe infini dénombrable est un mineur strict de lui-même". Précisez bien le sens de l'assertion et montrer qu'elle implique le théorème des mineurs.
   

Remarque : dans la littérature, la définition de bel ordre fait parfois appel à une relation de préordre (juste réflexive et transitive) plutôt que d'ordre. Cela explique que dans la littérature anglaise, on se réfère souvent aux well-quasi-orders ou WQO (quasi-order = préordre). Ceci-dit, quasiment tout le temps, les théorèmes et preuves restent identiques pour les deux définitions. D'autre part quasiment tous les exemples de beaux ordres étudiés sont des ordres. Pour finir, remarquer que tout ordre est un préordre et tout préordre peut se ramener à un ordre en quotientant par la relation d'équivalence x ∼ y ssi x ≤ y et y ≤ x. Il n'y a donc pas lieu de s'inquiéter ici de la définition choisie.

Quelques références (pas exhaustif).

• Graph Theory, livre de R. Diestel, Springer (2000). Dans le chapître 12, les sections 12.1 et 12.2 donnent des preuves et 12.5 discute du théorème des mineurs. Les questions 6, 7 et 8 correspondent à des exercices de ce chapître.
• Graph Minor Theory, article de L. Lovasz, Bulletin of the AMS 43 (2005). C'est une petite synthèse à propos du théorème des mineurs.
  

Retour à la page des sujets.