Antilánc

A matematikában az antilánc egy részbenrendezett halmaz olyan részhalmaza, melynek elemei közül semelyik kettő sem hasonlítható össze.

Egyes szerzők antilánc néven hivatkoznak az erős antiláncra, ami olyan részhalmaz, melynek semelyik két eleménél sem találunk kisebb elemet a részbenrendezett halmazban.

Legyen S egy részbenrendezett halmaz. Azt mondjuk, hogy a halmaz két eleme, a és b akkor összehasonlíthatók, ha vagy a ≤ b vagy b ≤ a. Ha például x és y-ra sem az x ≤ y, sem az y ≤ x nem áll fenn, akkor a két elem össze nem hasonlítható.

Az S halmazban egy lánc olyan C részhalmaz, melyben bármely elempár összehasonlítható; azaz C rendezett halmaz. Az S halmazban az A részhalmaz antilánc, amennyiben semelyik elempár sem hasonlítható össze egymással; tehát A semelyik két eleme között sincs rendezési reláció.

Antilánc szélessége és magassága

Maximális antilánc alatt olyan antiláncot értünk, ami nem valódi részhalmaza egyetlen más antiláncnak sem. A maximális antilánc számossága nagyobb vagy egyenlő bármely más antilánc számosságánál. A részbenrendezett halmaz szélessége megegyezik maximális antiláncának számosságával. Mivel bármely antilánc legfeljebb egyetlen közös elemet tartalmaz egy lánccal, ha a halmazt fel tudjuk osztani k láncra, akkor a részbenrendezett halmaz szélességének legfeljebb k-nak kell lennie. Dilworth tétele kimondja, hogy ezt a határt minden esetben el is lehet érni: mindig létezik olyan antilánc, és a halmaz elemeinek olyan láncokra bontása, hogy a láncok száma megegyezik az antilánc elemeinek számával, ami szintén megegyezik a részbenrendezett halmaz szélességével.

Hasonló módon definiálható egy részbenrendezett halmaz magassága, mely megegyezik a maximális lánc számosságával. A Dilworth-tétel duálisa, a Mirsky-tétel kimondja, hogy bármely véges magasságú részbenrendezett halmaznál a magasság megegyezik azzal a számmal, ahány antiláncra lehet bontani a részbenrendezett halmazt minimálisan.

Fordítás

• Ez a szócikk részben vagy egészben az Antichain című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

• Weisstein, Eric W.: Antichain (angol nyelven). Wolfram MathWorld