Antichaîne

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 ».

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.

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.

Dit autrement, étant donné ${\displaystyle E}$ un ensemble muni d'une relation d'ordre ${\displaystyle \leqslant }$, un sous-ensemble ${\displaystyle A}$ est une antichaîne de ${\displaystyle E}$ si pour tout ${\displaystyle x,y}$ de ${\displaystyle A}$,

${\displaystyle x\leqslant y{\text{ ou }}y\leqslant x\implies x=y.}$

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.

On peut noter que pour tout ensemble partiellement ordonné, l'intersection d'une antichaîne et d'une chaîne ne peut contenir au plus qu'un seul élément. Par le principe des tiroirs, on en déduit que si l'on partitionne cet ensemble en un nombre ${\displaystyle k}$ de chaînes (resp. d'antichaînes), la plus longue antichaîne (resp. chaîne) ne peut être de cardinal supérieur à ${\displaystyle k}$. De façon intéressante les deux bornes sont atteintes et ceci amène à définir la largeur et la hauteur de l'ensemble.

Le cardinal de la plus grande antichaîne d'un ensemble partiellement ordonné est la largeur de cet ensemble. De par le théorème de Dilworth^[2], la largeur correspond aussi au nombre minimale de chaînes nécessaires pour partitionner l'ensemble. Par dualité, la hauteur d'un ensemble partiellement ordonné correspond à la longueur de la plus grande chaîne de cet ensemble et au nombre minimal d'antichaînes nécessaire pour le partitionner, c'est le théorème de Mirsky^[3].

Les antichaînes d'un ensemble totalement ordonné sont les singletons et l'ensemble vide. Par conséquent, la largeur d'un ordre total est 1.

Soit ${\displaystyle {\mathcal {P}}(E)}$ l'ensemble des parties d'un ensemble donné ${\displaystyle E}$, muni de la relation d'inclusion, on appelle famille de Sperner une antichaîne de ${\displaystyle {\mathcal {P}}(E)}$.

Si ${\displaystyle E}$ est fini de cardinal ${\displaystyle n}$, le nombre d'antichaînes est un nombre de Dedekind ${\displaystyle M(n)}$, et La largeur de ${\displaystyle {\mathcal {P}}(E)}$ pour l'inclusion est, d'après le théorème de Sperner : ${\displaystyle {n \choose \lfloor {n/2}\rfloor }}$.

Prenons le cas particulier des parties d'un ensemble à 3 éléments ${\displaystyle \{x,y,z\}}$, dont la figure ci-dessous représente le diagramme de Hasse.

On compte en tout M(3) = 20 antichaines possibles. Ses antichaînes maximales sont :

• ${\displaystyle {\big \{}\varnothing {\big \}}}$, ${\displaystyle {\big \{}\{x,y,z\}{\big \}}}$
• ${\displaystyle {\big \{}\{x\},\{y,z\}{\big \}}}$, ${\displaystyle {\big \{}\{y\},\{x,z\}{\big \}}}$, ${\displaystyle {\big \{}\{z\},\{x,y\}{\big \}}}$
• ${\displaystyle {\big \{}\{x\},\{y\},\{z\}{\big \}}}$, ${\displaystyle {\big \{}\{x,y\},\{x,z\},\{y,z\}{\big \}}}$.

Sa largeur est égale à 3, le cardinal des deux plus grandes antichaînes, qui est bien égal à ${\displaystyle {3 \choose \lfloor {3/2}\rfloor }}$.

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

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

Un bel ordre est un ordre partiel bien fondé sans antichaîne infinie.

Les antichaînes sont utilisées en informatique comme une structure de données efficace en model checking^[4],[5].

• Antichaîne forte (en)
• Chaîne
• Théorème de Dilworth
• Famille de Sperner
• Nombre de dedekind

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

• Portail des mathématiques