Antichaîne

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] (Par opposition aux chaînes qui forment parties d'un ensemble dont les éléments sont toujours deux à deux comparables.)

Dit autrement, soit E un ensemble muni d'une relation d'ordre ≤, un sous-ensemble A est une antichaîne de E si pour tout x,y de A,

x\leq y{\text{ ou }}y\leq x\implies x=y.

Une antichaîne est dite maximale si elle n'est incluse (strictement) dans aucune autre antichaîne.

La famille 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. Dans le cas du treillis formé par les sous-ensembles d'un ensemble fini ordonnés par l'inclusion, les antichaînes sont connues comme les familles de Sperner, et compte un nombre de Dedekind d'éléments. De manière générale, dénombrer les antichaînes d'un ensemble est un problème #P-complet.

Largeur et hauteur d'un ensemble ordonné

On peut noter que pour tout ensemble partiellement ordonné, l'intersection d'une antichaîne et 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 $k$ de chaînes (resp. d'antichaînes), alors la plus longue antichaîne (resp. chaîne) ne peut être de cardinal supérieur à $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].

Exemples

Ordre total

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.

Ensemble des parties d'un ensemble et inclusion

Soit ${\mathcal {P}}(E)$ l'ensemble des parties d'un ensemble donné $E$ , muni de la relation d'inclusion, on appelle famille de Sperner une antichaîne de ${\mathcal {P}}(E)$ . Si $E$ est fini de cardinal n, la largeur de l'inclusion est alors, d'après le théorème de Sperner : ${n \choose \lfloor {n/2}\rfloor }$ .

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

Diagramme de Hasse d'un ensemble à 3 éléments.

Ses antichaînes maximales sont :

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

Sa largeur est égale à 3, le cardinal des deux plus grandes antichaînes.

ℕ muni de la divisibilité

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 2^kc avec c impair appartient à une antichaîne maximale (i.e. de cardinal n) si et seulement si 2n < 3^k + 1 c.

Antichaîne infinie

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

Applications en informatique

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

Voir aussi

Articles connexes

Lien externe

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

Références

Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, 2007 (lire en ligne), p. 19.
Robert P. Dilworth, « A decomposition theorem for partially ordered sets », Annals of Mathematics, vol. 51, n^o 1,‎ 1950, p. 161–166 (DOI 10.2307/1969503, JSTOR 1969503)
Leon Mirsky, « A dual of Dilworth's decomposition theorem », American Mathematical Monthly, vol. 78, n^o 8,‎ 1971, p. 876–877 (DOI 10.2307/2316481, JSTOR 2316481)
(en) M. De Wulf, L. Doyen, N. Maquet et J.-F. Raskin, « Antichains: Alternative Algorithms for LTL Satisfiability and Model-Checking », Tools and Algorithms for the Construction and Analysis of Systems, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 29 mars 2008, p. 63–77 (ISBN 9783540787990, DOI 10.1007/978-3-540-78800-3_6, lire en ligne, consulté le 1^er mars 2018)
(en) « Antichains »

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[Caspard73-1] Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, 2007 (lire en ligne), p. 19.

[2] Robert P. Dilworth, « A decomposition theorem for partially ordered sets », Annals of Mathematics, vol. 51, n^o 1,‎ 1950, p. 161–166 (DOI 10.2307/1969503, JSTOR 1969503)

[3] Leon Mirsky, « A dual of Dilworth's decomposition theorem », American Mathematical Monthly, vol. 78, n^o 8,‎ 1971, p. 876–877 (DOI 10.2307/2316481, JSTOR 2316481)

[4] (en) M. De Wulf, L. Doyen, N. Maquet et J.-F. Raskin, « Antichains: Alternative Algorithms for LTL Satisfiability and Model-Checking », Tools and Algorithms for the Construction and Analysis of Systems, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 29 mars 2008, p. 63–77 (ISBN 9783540787990, DOI 10.1007/978-3-540-78800-3_6, lire en ligne, consulté le 1^er mars 2018)

[5] (en) « Antichains »