Antilánc

A Wikipédiából, a szabad enciklopédiából

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 ab vagy ba. Ha például x és y-ra sem az xy, sem az yx 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[szerkesztés | forrásszöveg szerkesztése]

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 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.

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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.

Irodalom[szerkesztés | forrásszöveg szerkesztése]