Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Théorème de Dilworth
Résumé
Le théorème de Dilworth en théorie des ordres et en combinatoire, dû à Robert Dilworth, caractérise la largeur de tout ordre (partiel) fini en termes d'une partition de cet ordre en un nombre minimum de chaînes.
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.
La preuve suivante, par récurrence sur la taille de l'ensemble partiellement ordonné S, s'inspire de celle de Galvin.
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 C, ... , C, et une antichaîne A de T de cardinal k. Pour chaque i de 1 à k, il existe dans C des éléments appartenant à au moins une antichaîne de T de taille k (par exemple : les éléments communs à C et A) ; soient x le plus grand d'entre eux et A une telle antichaîne associée. Alors, l'ensemble A = {x, ... , x} est une antichaîne. En effet, pour tous indices i et j distincts, il existe au moins un y commun à A et C, et un tel élément vérifie y ≤ x (par définition de x), donc (puisque x ≱ y).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.