Antichaîne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Cet article ne cite pas suffisamment ses sources (juillet 2010).

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 » (modifier l'article, comment ajouter mes sources ?).

En mathématiques, plus précisément en théorie des ordres, une antichaîne d'un ensemble E muni d'une relation d'ordre (notée ici ≤ ) est une partie A de E telle que, pour tout x, y de A,

x \le y \Rightarrow x=y.

Autrement dit, dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables.

La largeur d'un ordre est le maximum des cardinaux de ses antichaînes (par exemple : un ordre total est un ordre de largeur 1).

Antichaînes de N[modifier | modifier le code]

Considérons l'ensemble N des entiers naturels, ordonné par la divisibilité.

Pour tout entier naturel n, la largeur de {1, 2, … , 2n} (muni de l'ordre induit) est n. De plus, dans cet ensemble ordonné, un élément de la forme 2kc avec c impair appartient à une antichaîne maximale (i.e. de cardinal n) si et seulement si 2n < 3k + 1 c.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Antichain », MathWorld