Ce théorème s’applique aux ensembles partiellement ordonnés (posets). C’est un ensemble où certains éléments peuvent être comparés (l’un est « plus petit » que l’autre), mais pas nécessairement tous.
- Une chaîne est un sous-ensemble où tous les éléments sont mutuellement comparables (comme une lignée d’ancêtres).
- Une antichaîne est un sous-ensemble où aucun couple d’éléments distincts n’est comparable (comme un groupe de frères et sœurs).
- La largeur d’un ensemble ordonné est la taille de la plus grande antichaîne possible.
- Le but est de recouvrir l’ensemble par un minimum de chaînes.
Pour tout ensemble partiellement ordonné fini, la taille de la plus grande antichaîne est égale au nombre minimum de chaînes nécessaires pour recouvrir l’ensemble.
Autrement dit : $$ \text{largeur}(P) = \min \{ k \mid P = C_1 \cup \dots \cup C_k, \text{ où les } C_i \text{ sont des chaînes} \} $$
Idée de la Démonstration
La démonstration n’est pas triviale. L’inégalité « facile » est que le nombre de chaînes est toujours supérieur ou égal à la taille de la plus grande antichaîne (car deux éléments d’une antichaîne ne peuvent pas être dans la même chaîne).
La partie difficile est de prouver l’égalité. La preuve la plus courante se fait par induction sur la taille de l’ensemble. Une autre preuve élégante établit une équivalence avec le théorème de König sur les graphes bipartis, qui est lui-même lié au théorème des mariages de Hall.
Dualité et Applications
- Théorème de Mirsky (dual) : Il existe un théorème dual qui affirme que la taille de la plus longue chaîne est égale au nombre minimum d’antichaînes nécessaires pour recouvrir l’ensemble.
- Combinatoire : Le théorème de Dilworth est un résultat central en combinatoire extrémale et en théorie des ordres.
- Informatique : Il a des applications en ordonnancement de tâches. Si la relation d’ordre est « la tâche A doit être faite avant la tâche B », une chaîne est une séquence de tâches qui doivent être faites en série, et une antichaîne est un ensemble de tâches qui peuvent être faites en parallèle. Le théorème relie le degré maximal de parallélisme possible au nombre minimum de processeurs (ou de « pas de temps ») nécessaires pour exécuter toutes les tâches.