Antichain

Antichain  je podmnožina částečně uspořádané množiny , ve které jsou libovolné dva odlišné prvky nesrovnatelné.

Maximální mohutnost antiřetězce částečně uspořádané množiny se nazývá jeho šířka ; podle Dilworthova teorému je šířka také rovna minimálnímu počtu řetězců (plně uspořádaných podmnožin), do kterých lze množinu rozdělit. Podle toho je výška částečně uspořádané množiny (délka jejího nejdelšího řetězce) podle Mirského teorému rovna minimálnímu počtu antiřetězců, na které lze tuto množinu rozdělit.

Rodina všech antiřetězců v konečné částečně uspořádané množině může být vybavena sjednocovacími a průnikovými operacemi, které z nich dělají distribuční mříž . Pro částečně uspořádaný systém všech podmnožin konečné množiny uspořádané inkluzí množin se antiřetězce nazývají Spernerovy rodiny a jejich mřížka je volná distributivní mřížka s Dedekindovým počtem prvků. Obecně platí, že problém počítání počtu antiřetězců konečné částečně uspořádané množiny je ♯P-complete .