Antichain - Antichain

V matematice , v oblasti teorie řádu , je antičíslo podmnožinou částečně uspořádané množiny tak, že jakékoli dva odlišné prvky v podmnožině jsou nesrovnatelné .

Velikost největšího antichainu v částečně uspořádané sadě je známá jako jeho šířka . Podle Dilworthovy věty se to také rovná minimálnímu počtu řetězců (zcela seřazených podmnožin), do kterých lze sadu rozdělit. Výška částečně uspořádané sady (délka jejího nejdelšího řetězce) se ve skutečnosti rovná Mirskyho větě minimálním počtem antičlánků, na které lze sadu rozdělit.

Rodině všech antičlánků v konečné částečně uspořádané sadě mohou být přiděleny operace spojování a splňování , což z nich dělá distribuční mřížku . Pro částečně uspořádaný systém všech podmnožin konečné množiny seřazených podle zahrnutí množiny se antičísla nazývají Spernerovy rodiny a jejich mřížka je volná distribuční mřížka s Dedekindovým počtem prvků. Obecněji platí, že počítání počtu řetězců konečné částečně uspořádané sady je #P-kompletní .

Definice

Budiž částečně objednaná sada. Dva prvky a částečně uspořádané množiny se nazývají srovnatelné, pokud nejsou dva prvky srovnatelné, nazývají se nesrovnatelné; to znamená, a jsou neporovnatelné, pokud ani jedno${\ displaystyle S}$${\ displaystyle a}$${\ displaystyle b}$${\ Displaystyle a \ leq b {\ text {nebo}} b \ leq a.}$${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle x \ leq y {\ text {nor}} y \ leq x.}$

Řetězec v je podmnožina, ve které je každý pár prvků srovnatelný; to znamená, že je zcela objednáno . Protiřetězec v je podmnožina z , ve které každá dvojice různých prvků je nesrovnatelná; to znamená, že neexistuje žádný příkaz vztah mezi dvěma různými prvky v (však někteří autoři používají termín „protiřetězec“ tak, že znamená silné protiřetězec , podmnožinu tak, že zde není žádný prvek uspořádané množiny menší než dva odlišné prvky protiřetězec. ) ${\ displaystyle S}$ ${\ Displaystyle C \ subseteq S}$${\ displaystyle C}$${\ displaystyle S}$ ${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle A.}$

Výška a šířka

Maximální protiřetězec je protiřetězec, který není vlastní podmnožinou jiného protiřetězec. Maximum protiřetězec je protiřetězec, která má mohutnost alespoň tak velký, jako každý jiný protiřetězec. Šířka o uspořádaná množina je mohutnost maximální protiřetězec. Každý protiřetězec mohou protínat jakýkoli řetězec v nejvýše jednoho prvku, takže, pokud se může rozdělit prvky objednávky do řetězců pak šířka objednávky musí být nejvýše (v případě, že protiřetězec má více než prvky, které rozškatulkovat princip , tam byly by 2 jeho prvky patřící do stejného řetězce, rozpor). Dilworthova věta uvádí, že této hranice lze vždy dosáhnout: vždy existuje antichain a rozdělení prvků do řetězců tak, že počet řetězců se rovná počtu prvků v antichainu, který se proto musí rovnat také šířce. Podobně lze definovat výšku částečného řádu jako maximální mohutnost řetězce. Mirskyho věta uvádí, že v jakémkoli dílčím pořadí konečné výšky se výška rovná nejmenšímu počtu antičlánků, na které lze pořadí rozdělit. ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Spernerovy rodiny

Antichain v zařazování podmnožin sady prvků je známý jako Spernerova rodina . Počet různých Spernerových rodin se počítá s čísly Dedekind , z nichž prvních je několik ${\ displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sekvence A000372 v OEIS ).

I prázdná množina má ve své mocenské sadě dvě antičísla: jednu obsahující jedinou sadu (samotná prázdná množina) a druhou neobsahující žádné sady.

Připojte se a setkejte se s operacemi

Jakýkoli řetězec odpovídá nižší sadě${\ displaystyle A}$

V konečném dílčím pořadí (nebo obecněji dílčím pořadí splňujícím podmínku vzestupného řetězce ) mají všechny nižší sady tuto formu. Sjednocení jakýchkoli dvou nižších sad je další nižší množinou a operace sjednocení odpovídá tímto způsobem operaci spojení na antičláncích: Podobně můžeme definovat operaci setkávání na antičláncích, což odpovídá průniku nižších množin: Operace spojování a setkávání na všech konečných antichains konečných podmnožin sady definují distribuční mřížku , volná distribuční mřížka generovaná Birkhoffovou reprezentační větou pro distribuční mřížky uvádí, že každou konečnou distribuční mřížku lze reprezentovat pomocí operací join and meet na antichains a konečný dílčí řád, nebo ekvivalentně jako operace sjednocení a průniku na nižších množinách dílčího řádu. ${\ displaystyle X}$${\ displaystyle X.}$

Výpočetní náročnost

Maximální antichain (a jeho velikost, šířka dané částečně uspořádané množiny) lze nalézt v polynomiálním čase . Počítání počtu řetězců v dané částečně seřazené sadě je #P-kompletní .

Reference

externí odkazy

• Weisstein, Eric W. „Antichain“ . MathWorld .
• „Antichain“ . PlanetMath .