Antikæde

En antikæde  er en delmængde af et delvist ordnet sæt , hvori to forskellige elementer er uforlignelige.

Den maksimale kardinalitet af en antikæde i et delvist ordnet sæt kaldes dens bredde ; ved Dilworths teorem er bredden også lig med det mindste antal kæder (fuldt ordnede delmængder), som et sæt kan opdeles i. Følgelig er højden af ​​et delvist ordnet sæt (længden af ​​dets længste kæde) lig, ifølge Mirskys sætning , med det mindste antal antikæder, som dette sæt kan opdeles i.

Familien af ​​alle antikæder i et endeligt delvist ordnet sæt kan udstyres med unions- og skæringsoperationer, hvilket gør dem til et distributivt gitter . For et delvist ordnet system af alle delmængder af et endeligt sæt ordnet efter inklusion af mængder, kaldes antikæder Sperner-familier , og deres gitter er et frit distributivt gitter med et Dedekind-antal af elementer. Generelt er problemet med at tælle antallet af antikæder i et endeligt delvist ordnet sæt ♯P-komplet .