Antichaîne - Antichain

En mathématiques , dans le domaine de la théorie de l' ordre , une antichaîne est un sous-ensemble d'un ensemble partiellement ordonné de telle sorte que deux éléments distincts du sous-ensemble soient incomparables .

La taille de la plus grande antichaîne dans un ensemble partiellement ordonné est connue sous le nom de largeur . D'après le théorème de Dilworth , cela équivaut également au nombre minimum de chaînes (sous-ensembles totalement ordonnés) dans lesquels l'ensemble peut être partitionné. Doublement, la hauteur de l'ensemble partiellement ordonné (la longueur de sa plus longue chaîne) est égale par le théorème de Mirsky au nombre minimum d'antichaînes dans lesquelles l'ensemble peut être partitionné.

La famille de toutes les antichaînes dans un ensemble fini partiellement ordonné peut recevoir des opérations de jointure et de rencontre , les transformant en un réseau distributif . Pour le système partiellement ordonné de tous les sous-ensembles d'un ensemble fini, ordonné par inclusion d'ensemble, les antichaînes sont appelées familles de Sperner et leur réseau est un réseau distributif libre , avec un nombre d'éléments de Dedekind . Plus généralement, compter le nombre d'antichaînes d'un ensemble fini partiellement ordonné est #P-complet .

Définitions

Soit un ensemble partiellement ordonné. Deux éléments et d'un ensemble partiellement ordonné sont dits comparables si Si deux éléments ne sont pas comparables, ils sont dits incomparables ; c'est-à-dire et sont incomparables si ni l'un ni l'autre

Une chaîne en est un sous - ensemble dans lequel chaque paire d'éléments est comparable ; qui est, est totalement ordonné . Une antichaîne dans est un sous - ensemble de dans lequel chaque paire d'éléments différents est incomparable ; c'est-à-dire qu'il n'y a pas de relation d'ordre entre deux éléments différents dans (Cependant, certains auteurs utilisent le terme "antichaîne" pour signifier une antichaîne forte , un sous-ensemble tel qu'il n'y a aucun élément du poset plus petit que deux éléments distincts de l'antichaîne. )

Hauteur et largeur

Une antichaîne maximale est une antichaîne qui n'est pas un sous - ensemble approprié d'une autre antichaîne. Une antichaîne maximale est une antichaîne qui a une cardinalité au moins aussi grande que toutes les autres antichaînes. La largeur d'un ensemble partiellement ordonné est la cardinalité d'une antichaîne maximale. Toute antichaîne peut intersecter n'importe quelle chaîne dans au plus un élément, donc, si nous pouvons partitionner les éléments d'un ordre en chaînes alors la largeur de l'ordre doit être au plus (si l'antichaîne a plus d' éléments, par le principe du pigeonhole , il serait 2 de ses éléments appartenant à la même chaîne, contradiction). Le théorème de Dilworth énonce que cette borne peut toujours être atteinte : il existe toujours une antichaîne, et une partition des éléments en chaînes, telle que le nombre de chaînes est égal au nombre d'éléments dans l'antichaîne, qui doit donc aussi être égale à la largeur. De même, on peut définir la hauteur d'un ordre partiel comme étant la cardinalité maximale d'une chaîne. Le théorème de Mirsky stipule que dans tout ordre partiel de hauteur finie, la hauteur est égale au plus petit nombre d'antichaînes dans lesquelles l'ordre peut être divisé.

Familles Sperner

Une antichaîne dans l'ordre d'inclusion des sous-ensembles d'un ensemble d'éléments est connue sous le nom de famille Sperner . Le nombre de familles de Sperner différentes est compté par les nombres de Dedekind , dont les premiers nombres sont

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (séquence A000372 dans l' OEIS ).

Même l'ensemble vide a deux antichaînes dans son ensemble de puissance : l'une contenant un seul ensemble (l'ensemble vide lui-même) et l'autre ne contenant aucun ensemble.

Rejoignez et rencontrez des opérations

Toute antichaîne correspond à un ensemble inférieur

Dans un ordre partiel fini (ou plus généralement un ordre partiel satisfaisant la condition de chaîne ascendante ) tous les ensembles inférieurs ont cette forme. L'union de deux ensembles inférieurs est un autre ensemble inférieur, et l'opération d'union correspond ainsi à une opération de jointure sur les antichaînes :
De même, on peut définir une opération de rencontre sur les antichaînes, correspondant à l'intersection des ensembles inférieurs :
Les opérations de jointure et de rencontre sur toutes les antichaînes finies de sous-ensembles finis d'un ensemble définissent un réseau distributif , le réseau distributif libre généré par le théorème de représentation de Birkhoff pour les réseaux distributifs stipule que chaque réseau distributif fini peut être représenté via des opérations de jointure et de rencontre sur les antichaînes d'un ordre partiel fini, ou de manière équivalente comme opérations d'union et d'intersection sur les ensembles inférieurs de l'ordre partiel.

Complexité de calcul

Une antichaîne maximale (et sa taille, la largeur d'un ensemble partiellement ordonné donné) peut être trouvée en temps polynomial . Compter le nombre d'antichaînes dans un ensemble partiellement ordonné donné est #P-complet .

Les références

Liens externes