| dbo:abstract
|
- A matematika, azon belül a és kombinatorika területén a Dilworth-tétel a véges részbenrendezett halmazok szélességét jellemzi minimális láncfelbontásuk figyelembe vételével. Nevét matematikusról kapta. Egy részbenrendezett halmazban lévő antilánc páronként össze nem hasonlítható elemek alkotta részhalmaz, míg a láncban lévő elemek páronként mind összehasonlíthatók. 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, és ezt a számosságot tekintjük a részbenrendezett halmaz szélességének. Legyen (P,≤) egy véges, részben rendezett halmaz, amelyben van n elemű antilánc, de nincs n+1 elemű antilánc. Ekkor P legkevesebb n darab lánccal fedhető le, azaz léteznek olyan c1, c2, ..., cn ≤ P láncok, hogy P = c1 c2 ... cn, de n-nél kevesebb láncra ez már nem igaz. A Dilworth-tétel így is kimondható: bármely véges részbenrendezett halmazban a maximális antilánc elemeinek száma megegyezik a láncok minimális számával a lehetséges láncfelbontások között. A tétel egy végtelen részbenrendezett halmazokra vonatkozó verziója szerint egy részbenrendezett halmaz szélessége pontosan akkor egyezik meg a véges w számmal, ha a halmaz w láncba felbontható, de kevesebbe nem. Duálisa a . (hu)
- A matematika, azon belül a és kombinatorika területén a Dilworth-tétel a véges részbenrendezett halmazok szélességét jellemzi minimális láncfelbontásuk figyelembe vételével. Nevét matematikusról kapta. Egy részbenrendezett halmazban lévő antilánc páronként össze nem hasonlítható elemek alkotta részhalmaz, míg a láncban lévő elemek páronként mind összehasonlíthatók. 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, és ezt a számosságot tekintjük a részbenrendezett halmaz szélességének. Legyen (P,≤) egy véges, részben rendezett halmaz, amelyben van n elemű antilánc, de nincs n+1 elemű antilánc. Ekkor P legkevesebb n darab lánccal fedhető le, azaz léteznek olyan c1, c2, ..., cn ≤ P láncok, hogy P = c1 c2 ... cn, de n-nél kevesebb láncra ez már nem igaz. A Dilworth-tétel így is kimondható: bármely véges részbenrendezett halmazban a maximális antilánc elemeinek száma megegyezik a láncok minimális számával a lehetséges láncfelbontások között. A tétel egy végtelen részbenrendezett halmazokra vonatkozó verziója szerint egy részbenrendezett halmaz szélessége pontosan akkor egyezik meg a véges w számmal, ha a halmaz w láncba felbontható, de kevesebbe nem. Duálisa a . (hu)
|
