Théorème de Dilworth
En mathématiques, plus précisément en théorie des ordres et en combinatoire, le théorème de Dilworth, dû à Robert Dilworth[1], caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.
Énoncé
Dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables et une chaîne est une partie dont les éléments sont deux à deux comparables. Le théorème de Dilworth établit, pour un ordre fini, l'existence d'une antichaîne A et d'une partition de l'ensemble ordonné en une famille P de chaînes, telles que A et P aient même cardinal. Pour de tels A et P, A est nécessairement une antichaîne de cardinal maximum (puisque toute antichaîne a au plus un élément dans chaque membre de P) et P est nécessairement une partition en chaînes de cardinal minimum (puisque toute partition en chaînes a au moins une chaîne par élément de A). La largeur de l'ordre partiel (i.e. la taille maximum d'une antichaîne) peut donc être redéfinie comme le cardinal commun de A et P, ou comme la taille minimum d'une partition en chaînes.
Une généralisation de ce théorème établit qu'un ordre (non nécessairement fini) est de largeur finie w si et seulement s'il peut être partitionné en w chaînes, mais pas moins.
Preuve par récurrence
La preuve suivante, par récurrence sur la taille de l'ensemble partiellement ordonné S, s'inspire de celle de Galvin[2].
Le résultat est immédiat si S est vide. Supposons donc S non vide, notons a l'un de ses éléments maximaux, et appliquons l'hypothèse de récurrence à l'ensemble ordonné T = S \ {a}. Il existe, pour un certain entier k, une partition de T en k chaînes CModèle:Ind, … , CModèle:Ind, et une antichaîne AModèle:Ind de T de cardinal k. Pour chaque i de 1 à k, il existe dans CModèle:Ind des éléments appartenant à au moins une antichaîne de T de taille k (par exemple : les éléments communs à CModèle:Ind et AModèle:Ind) ; soient xModèle:Ind le plus grand d'entre eux et AModèle:Ind une telle antichaîne associée. Alors, l'ensemble A = {xModèle:Ind, … , xModèle:Ind} est une antichaîne. En effet, pour tous indices i et j distincts, il existe au moins un y commun à AModèle:Ind et CModèle:Ind, et un tel élément vérifie y ≤ xModèle:Ind (par définition de xModèle:Ind), donc Modèle:Nobr (puisque xModèle:Ind ≱ y).
Revenons à S et distinguons deux cas.
- Si a majore l'un des xModèle:Ind, soit K la chaîne {a} ∪ {z ∈ CModèle:Ind | z ≤ xModèle:Ind}. Alors, par choix de xModèle:Ind, S \ K n'a pas d'antichaîne de taille k. L'hypothèse de récurrence implique alors que S \ K peut être partitionné en Modèle:Nobr chaînes, puisque A \ {xModèle:Ind} est une antichaîne de taille k – 1 de S \ K. Ceci partitionne S en k chaînes, comme souhaité.
- Sinon, A ∪ {a} est une antichaîne de taille k + 1 de S (puisque a est maximal dans S), or S est partitionné en k + 1 chaînes, {a}, CModèle:Ind, … , CModèle:Ind, ce qui termine la preuve.
Équivalence avec le théorème de Kőnig
Comme beaucoup d'autres résultats de combinatoire, parmi lesquels le lemme des mariages de Hall[3], le théorème de Dilworth est équivalent au théorème de Kőnig sur les couplages d'un graphe biparti.
Pour déduire du théorème de Kőnig le théorème de Dilworth, pour un ensemble partiellement ordonné S à n éléments, on définit un graphe biparti G = (U, V, E) par : U = V = S et un élément u de U est joint à un élément v de V par une arête de G lorsque u < v dans S. D'après le théorème de Kőnig, il existe dans G un couplage M et un transversal C de même cardinal m. Soit A l'ensemble des éléments de S qui ne correspondent à aucun sommet de C ; alors A a au moins n – m éléments (éventuellement plus, si C contient des sommets dans U et V correspondant au même élément de S). Par définition d'un transversal, chaque arête a une extrémité dans C, et donc A est une antichaîne. Soit P la famille des chaînes formées en plaçant x et y dans la même chaîne chaque fois qu'ils sont joints par une arête de M ; alors P a n – m chaînes. On a donc construit une antichaîne et une partition en chaînes de même cardinal.
Réciproquement, pour déduire du théorème de Dilworth le théorème de Kőnig, pour un graphe biparti G = (U, V, E), on ordonne les sommets de G en posant : u < v si et seulement si u est dans U, v dans V, et une arête de E les relie. D'après le théorème de Dilworth, il existe une antichaîne A et une partition en chaînes P de même taille. Mais les seules chaînes non triviales sont ici les paires d'éléments correspondant aux arêtes du graphe, donc les chaînes non triviales de P forment un couplage. Le complémentaire de A forme un transversal de même cardinal que ce couplage.
Ce lien avec les couplages de graphes bipartis permet de calculer la largeur de tout ordre partiel fini en temps polynomial.
Généralisation aux ordres partiels infinis
Sur un ensemble infini T, un ordre est encore de largeur inférieure ou égale à un entier w (si et) seulement si T est réunion de w chaînes disjointes.
En effet un ensemble ordonné S est réunion de w chaînes disjointes si et seulement s'il existe une coloration par w couleurs du graphe d'incomparabilité de S (le graphe non orienté dont les sommets sont les éléments de S et les arêtes relient les paires d'éléments incomparables). Par conséquent, si la largeur de l'ordre sur T est inférieure ou égale à w alors, pour toute partie finie S de T (de largeur a fortiori majorée par w), il existe, d'après la version finie du théorème de Dilworth, une coloration par w couleurs du graphe d'incompatibilité de S. D'après le théorème de De Bruijn-Erdős, le graphe d'incomparabilité de T est alors, lui aussi, « w-colorable », donc T est réunion de w chaînes disjointes[4].
Cependant, le théorème ne s'étend pas aux ordres de largeur infinie : pour tout cardinal infini κ, il existe un ordre dont toute antichaîne est finie mais dont toutes les partitions en chaînes sont de taille au moins κ[4].
Micha Perles[5] étudie des analogues du théorème de Dilworth dans le cas infini.
Théorème dual de Mirsky
Le Modèle:Lien, dual de celui de Dilworth, établit que dans un ordre partiel, la taille maximum des chaînes, si elle est finie, est égale à la plus petite taille d'une partition en antichaînes[6]. La preuve en est bien plus simple : pour tout élément x, soit N(x) la taille maximum des chaînes dont x est le plus grand élément, alors les [[image réciproque|NModèle:Exp({i})]] forment une partition en n antichaînes, si n est la taille maximum des chaînes.
Perfection des graphes de comparabilité
Le graphe de comparabilité d'un ensemble ordonné est le graphe non orienté dont les sommets sont les éléments de l'ensemble et les arêtes relient les paires d'éléments comparables. Une clique dans ce graphe correspond donc à une chaîne, et un stable à une antichaîne. Tout sous-graphe induit d'un graphe de comparabilité est lui-même un graphe de comparabilité : celui de l'ordre restreint à ses sommets.
Un graphe non orienté est parfait si, dans tout sous-graphe induit, le nombre chromatique est égal à la taille de la plus grande clique. Tout graphe de comparabilité est parfait : c'est essentiellement le théorème de Mirsky, reformulé en termes de théorie des graphes[7]. D'après le théorème des graphes parfaits de Lovász, le complémentaire de tout graphe parfait est aussi parfait. Par conséquent, le complémentaire de tout graphe de comparabilité est parfait ; c'est une reformulation du théorème de Dilworth en termes de théorie des graphes[7], ce qui en fournit une autre preuve.
Largeur d'ordres particuliers
- Le treillis booléen BModèle:Ind est l'ensemble des parties d'un ensemble X à n éléments – essentiellement {1, 2, … , n} – ordonné par inclusion. Le théorème de Sperner assure que la taille maximum des antichaînes de BModèle:Ind est celle obtenue en choisissant, comme parties non comparables de X, celles de taille médiane :
L'inégalité de Lubell-Yamamoto-Meshalkin concerne aussi les antichaînes d'un ensemble de parties et peut être utilisée pour démontrer ce théorème. - Si l'on ordonne les entiers de l'intervalle [1, 2n] par divisibilité, le sous-intervalle [n + 1, 2n] forme une antichaîne de cardinal n. Il est d'autre part facile de partitionner cet ordre en n chaînes en prenant, pour chaque entier impair m de [1, 2n], la chaîne des nombres de la forme m2Modèle:Exp. D'après le théorème de Dilworth, cet ordre est donc de largeur n.
- Le théorème d'Erdős-Szekeres sur les sous-suites monotones peut être interprété comme une application du théorème de Dilworth à des ordres partiels de Modèle:Lien égale à 2[8].
- La « dimension convexe » d'un Modèle:Lien est le plus petit nombre de chaînes nécessaires pour définir cet antimatroïde, et le théorème de Dilworth peut servir à démontrer que ce nombre est égal à la largeur d'un ordre partiel associé, ce qui conduit à un algorithme en temps polynomial pour le calcul de la dimension convexe[9].
Notes et références
Modèle:Traduction/Référence Modèle:Références
Voir aussi
Article connexe
Liens externes
- Modèle:En Modèle:Pdf Modèle:Lien web
- Modèle:Planetmath
- Modèle:En Modèle:Pdf Modèle:Lien web
- Modèle:En Modèle:Lien web
- Modèle:MathWorld
- ↑ Modèle:Article.
- ↑ Modèle:Article.
- ↑ Modèle:Article.
- ↑ 4,0 et 4,1 Modèle:Ouvrage.
- ↑ Modèle:Article.
- ↑ Modèle:Article.
- ↑ 7,0 et 7,1 Modèle:Ouvrage.
- ↑ Modèle:Chapitre.
- ↑ Modèle:Article.