Antichaîne
De Wikipedia, l'encyclopédie encyclopedia
En mathématiques, plus précisément en théorie des ordres, une antichaîne est une partie d'un ensemble partiellement ordonné dont les éléments sont deux à deux incomparables[1]. La notion est ainsi nommée par opposition aux chaînes qui sont des parties d'un ensemble ordonné dont les éléments sont toujours deux à deux comparables.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Dit autrement, étant donné un ensemble muni d'une relation d'ordre , un sous-ensemble est une antichaîne de si pour tout de ,
Une antichaîne est dite maximale si elle n'est incluse (strictement) dans aucune autre antichaîne.
L'ensemble de toutes les antichaînes d'un ensemble fini partiellement ordonné peut être muni des opérations d'union et d'intersection pour en faire un treillis distributif.
Dénombrer les antichaînes d'un ensemble ordonné fini est un problème #P-complet.