Antyłańcuch - Antichain

W matematyce , w dziedzinie teorii porządku , antyłańcuch jest podzbiorem zbioru częściowo uporządkowanego, tak że dowolne dwa odrębne elementy w podzbiorze są nieporównywalne .

Rozmiar największego antyłańcucha w częściowo zamówionym zestawie jest znany jako jego szerokość . Według twierdzenia Dilwortha jest to również równe minimalnej liczbie łańcuchów (całkowicie uporządkowanych podzbiorów), na które można podzielić zbiór. Podwójnie wysokość częściowo uporządkowanego zbioru (długość jego najdłuższego łańcucha) równa się według twierdzenia Mirsky'ego minimalnej liczbie antyłańcuchów, na które zbiór może być podzielony.

Rodzinie wszystkich antyłańcuchów w skończonym, częściowo uporządkowanym zestawie można nadać operacje łączenia i spotykania , czyniąc z nich siatkę rozdzielczą . Dla częściowo uporządkowanego systemu wszystkich podzbiorów zbioru skończonego, uporządkowanego przez włączenie zbioru, antyłańcuchy nazywane są rodzinami Spernera, a ich sieć jest swobodną siecią rozdzielczą z liczbą elementów Dedekind . Bardziej ogólnie, liczenie liczby antyłańcuchów skończonego częściowo uporządkowanego zbioru to #P-zupełne .

Definicje

Niech będzie częściowo uporządkowanym zestawem. Dwa elementy i częściowo uporządkowanego zbioru nazywamy porównywalnymi, jeśli dwa elementy nie są porównywalne, nazywamy je nieporównywalnymi; to znaczy i są nieporównywalne, jeśli żadne${\displaystyle S}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a\leq b{\tekst{lub}}b\leq a.}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\leq y{\tekst{ani}}y\leq x.}$

Łańcuch w to podzbiór, w którym każda para elementów jest porównywalna; czyli jest całkowicie uporządkowane . Antyłańcuch w jest podgrupa o w którym każda para różnych elementów jest nieporównywalny; oznacza to, że nie ma związku kolejność pomiędzy dwoma różnymi elementami w (Jednakże, niektórzy autorzy termin „antyłańcuch” oznacza silne antyłańcuch , podzbiór taki sposób, że nie ma element poset mniejszy niż dwa różne elementy składające się na antyłańcuch. ) ${\displaystyle S}$ ${\displaystyle C\subseteq S}$${\ Displaystyle C}$${\displaystyle S}$ ${\ Displaystyle A}$${\displaystyle S}$${\ Displaystyle A.}$

Wysokość i szerokość

Maksymalny antyłańcuch jest antyłańcuch że nie jest właściwy podzbiór jakiejkolwiek innej antyłańcuch. Maksymalna antyłańcuch jest antyłańcuch że ma liczność co najmniej tak duża, jak w każdym innym antyłańcuch. Szerokość o częściowy porządek jest liczność maksymalnej antyłańcuch. Wszelkie antyłańcuch mogą się przecinać dowolny łańcuch w co najwyżej jeden element, więc jeśli możemy podzielić elementy o porządek w łańcuchach następnie szerokość rzędu muszą być co najwyżej (jeśli antyłańcuch ma więcej niż elementów, przez zasady zaszufladkować , nie byłoby 2 z jego elementów należących do tego samego łańcucha, sprzeczność). Twierdzenie Dilwortha mówi, że to ograniczenie można zawsze osiągnąć: zawsze istnieje antyłańcuch i podział elementów na łańcuchy, tak że liczba łańcuchów jest równa liczbie elementów w antyłańcuchu, który zatem musi być równy szerokości. Podobnie można zdefiniować wysokość rzędu częściowego jako maksymalną liczność łańcucha. Twierdzenie Mirsky'ego mówi, że w dowolnym cząstkowym rzędzie o skończonej wysokości wysokość jest równa najmniejszej liczbie antyłańcuchów, na które można podzielić ten rząd. ${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$

Rodziny Spernerów

Antyłańcuch w kolejności włączania podzbiorów zbioru -elementów jest znany jako rodzina Sperner . Liczba różnych rodzin Spernerów jest liczona przez liczby Dedekind , z których kilka pierwszych liczb to ${\ Displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sekwencja A000372 w OEIS ).

Nawet pusty zestaw ma w swoim zestawie mocy dwa antyłańcuchy: jeden zawierający pojedynczy zestaw (sam pusty zestaw) i drugi nie zawierający zestawów.

Dołącz i poznaj operacje

Każdy antyłańcuch odpowiada niższemu zestawowi${\ Displaystyle A}$

W skończonym częściowym porządku (lub ogólniej częściowym porządku spełniającym warunek rosnącego łańcucha ) wszystkie niższe zbiory mają tę postać. Łączenie dowolnych dwóch niższych zbiorów jest kolejnym niższym zbiorem, a operacja łączenia odpowiada w ten sposób operacji łączenia na antyłańcuchach:

$${\ Displaystyle A \ vee B = \ {x \ w A \ filiżanka B: \ dalej istnieje r \ w A \ filiżanka B {\ mbox {takie, że}} x <y \}.}$$

Podobnie możemy zdefiniować operację spełnienia na antyłańcuchach, odpowiadającą przecięciu dolnych zbiorów:

$${\ Displaystyle A \ klin B = \ {x \ w L_ {A} \ cap L_ {B}: \ dalej r \ w L_ {A} \ cap L_ {B} {\ mbox {tak, że}} x <y \}.}$$

Operacje złączenia i spełnienia na wszystkich skończonych antyłańcuchach skończonych podzbiorów zbioru definiują kratę rozdzielczą , swobodna krata rozdzielcza wygenerowana przez twierdzenie Birkhoffa o reprezentacji krat rozdzielczych stwierdza, że ​​każda skończona krata rozdzielcza może być reprezentowana przez operacje łączenia i spotykania na antyłańcuchach skończony porządek częściowy lub równoważnie jako operacje sumy i przecięcia na niższych zbiorach rzędu częściowego. ${\ Displaystyle X}$${\ Displaystyle X.}$

Złożoność obliczeniowa

Maksymalny antyłańcuch (i jego rozmiar, szerokość danego częściowo uporządkowanego zestawu) można znaleźć w czasie wielomianowym . Liczenie liczby antyłańcuchów w danym częściowo uporządkowanym zestawie to #P-complete .

Bibliografia

Linki zewnętrzne

• Weisstein, Eric W. „Antichain” . MatematykaŚwiat .
• „Antyłańcuch” . PlanetMath .