Antikedja

En antikedja  är en delmängd av en partiellt ordnad uppsättning där två distinkta element är ojämförbara.

Den maximala kardinaliteten för en antikedja i en delvis ordnad uppsättning kallas dess bredd ; enligt Dilworths teorem är bredden också lika med det minsta antalet kedjor (fullständigt ordnade delmängder) som en uppsättning kan delas in i. Följaktligen är höjden på en delvis ordnad uppsättning (längden på dess längsta kedja) lika, enligt Mirskys sats , med det minsta antalet antikedjor som denna uppsättning kan delas in i.

Familjen av alla antikedjor i en ändlig, delvis ordnad uppsättning kan utrustas med unions- och skärningsoperationer, vilket gör dem till ett distributivt gitter . För ett partiellt ordnat system av alla delmängder av en ändlig mängd ordnade efter inkludering av mängder, kallas antikedjor Sperner-familjer , och deras gitter är ett fritt distributionsgitter med ett antal Dedekind- element. I allmänhet är problemet med att räkna antalet antikedjor i en ändlig partiellt ordnad uppsättning ♯P-komplett .