Antichaîne

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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]

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,

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

La largeur d'un ordre est le maximum des cardinaux de ses antichaînes.

Exemples[modifier | modifier le code]

Ordre total[modifier | modifier le code]

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[modifier | modifier le code]

Soit l'ensemble des parties d'un ensemble donné , muni de la relation d'inclusion, on appelle famille de Sperner une antichaîne de . Si est fini de cardinal n, la largeur de l'inclusion est alors, d'après le théorème de Sterner : .

Prenons le cas particulier des parties d'un ensemble à 3 éléments , 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 :

  • ,
  • , ,
  • , .

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

ℕ muni de la divisibilité[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.

Antichaîne infinie[modifier | modifier le code]

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

Applications en informatique[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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

Références[modifier | modifier le code]

  1. Nathalie Caspard, Bruno Leclerc et Bernard Monjardet, Ensembles ordonnés finis : concepts, résultats et usages, Springer, (lire en ligne), p. 19.
  2. (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, série Lecture Notes in Computer Science,‎ , p. 63–77 (ISBN 9783540787990, DOI 10.1007/978-3-540-78800-3_6, lire en ligne, consulté le 1er mars 2018)
  3. (en) « Antichains »