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 x0, x1, x2, .... d'éléments de X, on peut extraire deux indices i<j tels que xi≤xj.

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 :
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 :
  2. Donner des exemples et des contre-exemples simples de beaux ordres. Par exemple est-ce que Nk 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=u1...up et v=v1...vq, on a u ≤ v s'il existe f injection de {1,...,p} dans {1,...,q} telle que ∀ i, ui ≤ vf(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).
Retour à la page des sujets.