Dilworth-tétel
A matematika, azon belül a rendezéselmélet é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 Mirsky-tétel.

Bizonyítás indukcióval 
Alább olvasható egy a részben rendezett halmaz méretére vonatkozó teljes indukciós bizonyítás, a következő alapján: .

Legyen  egy véges részbenrendezett halmaz. A tétel triviálisan igaz, ha  az üres halmaz. Tegyük fel ezért, hogy -nek legalább egy eleme van, és legyen  a -beli maximális elem.

Tételezzük fel, hogy valamely  egész számra a  részbenrendezett halmaz lefedhető  darab  diszjunkt lánccal, és rendelkezik legalább egy  méretű  antilánccal. Nyilvánvaló, hogy  az  értékekre. Az  értékekre legyen  a -beli olyan maximális elem, ami  egy  méretű antiláncához, valamint az  halmazhoz tartozik.
Azt állítjuk, hogy  egy antilánc.
Legyen  az -t tartalmazó,  méretű antilánc. Válasszunk ki 1-1 egymástól eltérő  és  indexet. Ekkor . Legyen . Ekkor , az  definíciója alapján. Ebből következik, hogy , hiszen . Az  és  szerepét felcserélve, megállapíthatjuk azt is, hogy . Ez igazolja, hogy  antilánc.

Térjünk vissza a -hez. Elsőként tegyük fel, hogy  valamely -re. Legyen  az  lánc. Ekkor az  alkalmas megválasztása miatt,  nem rendelkezik  méretű antilánccal. Ekkor az indukcióból következik, hogy  lefedhető  diszjunkt lánccal, hiszen  a  egy  méretű antilánca. Tehát a  a kívánalmaknak megfelelően lefedhető  diszjunkt lánccal. Következőkben, ha minden -re , akkor  a -ben egy  méretű antilánc (mivel  maximális -ben). Így  lefedhető a   db lánccal, teljessé téve a bizonyítást.

Bizonyítása a Kőnig-tétellel

Mint számos kombinatorikai eredmény, a Dilworth-tétel is egyenértékű a páros gráfokra vonatkozó Kőnig-tétellel és számos más kapcsolódó tétellel, köztük a Hall-tétellel is .

A Dilworth-tétel Kőnig-tétellel történő bizonyításához vegyük az n elemen meghatározott S részbenrendezést, határozzuk meg a G = (U,V,E) páros gráfot, ahol U = V = S és ahol (u,v) akkor határoz meg egy G-beli élet, ha u < v S-ben. A Kőnig-tétel alapján létezik G-ben egy M párosítás, illetve egy G-beli C csúcshalmaz úgy, hogy a gráf minden éle legalább egy C-beli csúcsot tartalmaz, és M-nek és C-nek ugyanaz az m a számossága. Legyen A S azon elemeinek a halmaza, melyek nem felelnek meg C egyik csúcsának sem; ekkor A legalább n − m elemmel rendelkezik (többel is rendelkezhet, ha a C tartalmaz a párosítás mindkét oldalának megfelelő elemeket). Legyen P láncok olyan halmaza, melyet úgy kapunk, hogy x és y akkor kerül ugyanabba a láncba, ha az M-ben létezik az (x,y) él; ekkor P n − m láncból áll. Tehát konstruáltunk egy antiláncot, és egy vele azonos számosságú láncfelbontást.

Megfordítva, a Kőnig-tétel bizonyítása a Dilworth-tételből levezetve így hangzik. Legyen G = (U,V,E) páros gráf, vegyük G csúcsain egy részbenrendezést, melyben pontosan akkor u < v, ha u az U-ban, v a V-ben található és létezik egy E él u és v között. A Dilworth-tétel alapján létezik azonos méretű A antilánc és P láncfelbontás. De a részbenrendezés nemtriviális láncai kizárólag olyan elempárok, melyek a gráf éleinek felelnek meg, tehát P nemtriviális láncai a gráf párosítását adják. Az A komplementere a G-nek a párosítással megegyező számosságú csúcslefedését alkotja.

A párosítással való kapcsolat miatt bármely részbenrendezés szélessége polinom időben kiszámítható. Precízebben, egy n elemű, k szélességű részbenrendezés O(kn2) időben detektálható .

Kiterjesztése végtelen részbenrendezett halmazokra
Dilworth tételének végtelen részbenrendezett halmazokra való kiterjesztése azt állítja, hogy egy részbenrendezett halmaz pontosan akkor rendelkezik véges w szélességgel, ha w láncba felbontható. Hiszen, tegyük fel hogy egy P végtelen részben rendezés szélessége w, ami azt jelenti, hogy bármely antiláncnak legfeljebb véges, w eleme lehet. P bármely S részhalmazának w láncfelbontása (ha az létezik) felfogható az S összehasonlíthatatlansági gráfja (a gráf, melynek csúcsai az S elemeinek felelnek meg, két csúcs között pedig akkor húzódik él, ha a halmaz két eleme nem összehasonlítható) egy w színnel történő színezéseként; a jó színezés minden színosztályának láncnak kell lennie. Feltételezve, hogy P szélessége w, és a Dilworth-tétel véges változatából következik, hogy P minden véges S részhalmazának w-színezhető az összehasonlíthatatlansági gráfja. Ezért a de Bruijn–Erdős-tétel alapján kijelenthető, hogy P-nek magának is w-színezhető az összehasonlíthatatlansági gráfja, ezért létezik a kívánt láncfelbontása .

A tétel nem terjeszthető ki ugyanilyen könnyedséggel arra az esetre, amikor nem csak a halmaz számossága, hanem a részben rendezés szélessége is végtelen. Ebben az esetben a legnagyobb antilánc mérete és a minimális láncfelbontás mérete egymástól nagyon különböző is lehet. Elmondható, hogy bármely κ végtelen kardinális számhoz tartozik olyan ℵ0 szélességű részben rendezés, melynek a minimális láncfelbontásában κ lánc található .

 tárgyalja a Dilworth-tétel végtelen analógiáit.

A Dilworth-tétel duálisa (a Mirsky-tétel)

A Dilworth-tétel egy duálisa kimondja, hogy egy részbenrendezés legnagyobb láncának mérete (ha az véges), megegyezik a minimális antilánc-felbontás méretével . A bizonyítás sokkal egyszerűbb, mint a Dilworth-tétel esetében: bármely x elemnél tekintsük azokat a láncokat, melyeknek x a legnagyobb eleme, és jelölje N(x) a legnagyobb ilyen x-maximális lánc méretét. Ekkor minden N−1(i) halmaz, ami az N egyenlő értékeit tartalmazza, egy antilánc, és ezek az antiláncok a legnagyobb lánccal megegyező darabra bontják fel a részben rendezést.

Az összehasonlíthatósági gráfok perfektsége
Egy összehasonlíthatósági gráf olyan irányítatlan gráf, amiben egy részbenrendezett halmaz (poset) azon elemeinek megfelelő csúcsok vannak összekötve. Így az összehasonlíthatósági gráf klikkjei a részben rendezés egy-egy láncának felel meg, a független csúcshalmazai pedig egy-egy antiláncnak. A részbenrendezés tulajdonságai miatt az összehasonlíthatósági gráfok bármely feszített részgráfja is összehasonlíthatósági gráf.

Egy irányítatlan gráf akkor perfekt, ha minden feszített részgráfjának kromatikus száma megegyezik a legnagyobb klikkjének méretével. Az, hogy minden összehasonlíthatósági gráf perfekt, lényegében csak a Mirsky-tétel egy gráfelméleti megfogalmazása . A -féle (gyenge) perfektgráf-tétel szerint bármely perfekt gráf komplementere is perfekt. Ezért bármely összehasonlíthatósági gráf komplementere is perfekt, ami viszont egyszerűen a Dilworth-tétel gráfelméleti megfogalmazása . Más szóval, a perfekt gráfok komplementer-tulajdonsága a Dilworth-tétel alternatív bizonyítását adhatja.

Néhány egyedi részbenrendezés szélessége
A Bn Boole-háló az n elemű X halmaz – lényegében {1, 2, …, n} – hatványhalmaza, melyet a tartalmazás (részhalmaz) reláció alapján rendezünk; jelölése (2[n], ⊆). A Sperner-tétel kimondja, hogy Bn egy maximális antiláncának mérete legfeljebb

Másképp fogalmazva, az X össze nem hasonlítható részhalmazainak legnagyobb családját az X medián méretű részhalmazainak kiválasztásával kapjuk. A Lubell–Yamamoto–Meshalkin-egyenlőtlenség szintén hatványhalmazok antiláncaival foglalkozik, és alkalmas a Sperner-tétel igazolására.

Ha az [1, 2n] intervallum egészeit oszthatóság alapján rendezzük, a [n + 1, 2n] részintervallum n számosságú antiláncot alkot. Ennek a rendezésnek n láncba való felbontása könnyen elérhető: Az [1,2n] intervallum minden páratlan m egésze láncot alkot az m2i alakú számokkal. Ezért a Dilworth-tétel alapján ennek a részbenrendezésnek a szélessége n.

A végtelen sorozatok monoton részsorozataira vonatkozó Erdős–Szekeres-tétel felfogható a Dilworth-tétel 2 rendezési dimenziójú részben rendezésekre való alkalmazásaként is .

Egy antimatroid „konvex dimenziója” alatt az antimatroid meghatározásához szükséges láncok minimális számát értjük, és a Dilworth-tétel segítségével megmutatható, hogy ez megegyezik a hozzá tartozó részben rendezés szélességével; emiatt létrehozható a konvex dimenziót polinom időben meghatározó algoritmus .

Fordítás

Jegyzetek

.
.
.
.
.
.
.
.
.
.
.

További információk 
 Equivalence of seven major theorems in combinatorics
  
 
 
 

Kombinatorikai tételek
Perfekt gráfok
A matematika , azon belül a rendezéselmélet é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 Mirsky-tétel . Bizonyítás indukcióval Alább olvasható egy a részben rendezett halmaz méretére vonatkozó teljes indukciós bizonyítás , a következő alapján : \ . Legyen egy véges részbenrendezett halmaz . A tétel triviálisan igaz , ha az üres halmaz . Tegyük fel ezért , hogy -nek legalább egy eleme van , és legyen a -beli maximális elem . Tételezzük fel , hogy valamely egész számra a részbenrendezett halmaz lefedhető darab diszjunkt lánccal , és rendelkezik legalább egy méretű antilánccal . Nyilvánvaló , hogy az értékekre . Az értékekre legyen a -beli olyan maximális elem , ami egy méretű antiláncához , valamint az halmazhoz tartozik . Azt állítjuk , hogy egy antilánc . Legyen az -t tartalmazó , méretű antilánc . Válasszunk kiegymástól eltérő és indexet . Ekkor \ . Legyen \ . Ekkor , az definíciója alapján . Ebből következik , hogy , hiszen \ . Az és szerepét felcserélve , megállapíthatjuk azt is , hogy \ . Ez igazolja , hogy antilánc . Térjünk vissza a -hez . Elsőként tegyük fel , hogy valamely -re . Legyen az lánc . Ekkor az alkalmas megválasztása miatt , nem rendelkezik méretű antilánccal . Ekkor az indukcióból következik , hogy lefedhető diszjunkt lánccal , hiszen a egy méretű antilánca . Tehát a a kívánalmaknak megfelelően lefedhető diszjunkt lánccal . Következőkben , ha minden -re , akkor a -ben egy méretű antilánc ( mivel maximális -ben ) . Így lefedhető a db lánccal , teljessé téve a bizonyítást . Bizonyítása a Kőnig-tétellel Mint számos kombinatorikai eredmény , a Dilworth-tétel is egyenértékű a páros gráfokra vonatkozó Kőnig-tétellel és számos más kapcsolódó tétellel , köztük a Hall-tétellel is \ . A Dilworth-tétel Kőnig-tétellel történő bizonyításához vegyük az n elemen meghatározott S részbenrendezést , határozzuk meg a G = ( U,V,E ) páros gráfot , ahol U = V = S és ahol ( u,v ) akkor határoz meg egy G-beli élet , ha u < v S-ben . A Kőnig-tétel alapján létezik G-ben egy M párosítás , illetve egy G-beli C csúcshalmaz úgy , hogy a gráf minden éle legalább egy C-beli csúcsot tartalmaz , és M-nek és C-nek ugyanaz az m a számossága . Legyen A S azon elemeinek a halmaza , melyek nem felelnek meg C egyik csúcsának sem ; ekkor A legalább n − m elemmel rendelkezik ( többel is rendelkezhet , ha a C tartalmaz a párosítás mindkét oldalának megfelelő elemeket ) . Legyen P láncok olyan halmaza , melyet úgy kapunk , hogy x és y akkor kerül ugyanabba a láncba , ha az M-ben létezik az ( x,y ) él ; ekkor P n − m láncból áll . Tehát konstruáltunk egy antiláncot , és egy vele azonos számosságú láncfelbontást . Megfordítva , a Kőnig-tétel bizonyítása a Dilworth-tételből levezetve így hangzik . Legyen G = ( U,V,E ) páros gráf , vegyük G csúcsain egy részbenrendezést , melyben pontosan akkor u < v , ha u az U-ban , v a V-ben található és létezik egy E él u és v között . A Dilworth-tétel alapján létezik azonos méretű A antilánc és P láncfelbontás . De a részbenrendezés nemtriviális láncai kizárólag olyan elempárok , melyek a gráf éleinek felelnek meg , tehát P nemtriviális láncai a gráf párosítását adják . Az A komplementere a G-nek a párosítással megegyező számosságú csúcslefedését alkotja . A párosítással való kapcsolat miatt bármely részbenrendezés szélessége polinom időben kiszámítható . Precízebben , egy n elemű , k szélességű részbenrendezés O( kn2 ) időben detektálható \ . Kiterjesztése végtelen részbenrendezett halmazokra Dilworth tételének végtelen részbenrendezett halmazokra való kiterjesztése azt állítja , hogy egy részbenrendezett halmaz pontosan akkor rendelkezik véges w szélességgel , ha w láncba felbontható . Hiszen , tegyük fel hogy egy P végtelen részben rendezés szélessége w , ami azt jelenti , hogy bármely antiláncnak legfeljebb véges , w eleme lehet. P bármely S részhalmazának w láncfelbontása ( ha az létezik ) felfogható az S összehasonlíthatatlansági gráfja ( a gráf , melynek csúcsai az S elemeinek felelnek meg , két csúcs között pedig akkor húzódik él , ha a halmaz két eleme nem összehasonlítható ) egy w színnel történő színezéseként ; a jó színezés minden színosztályának láncnak kell lennie . Feltételezve , hogy P szélessége w , és a Dilworth-tétel véges változatából következik , hogy P minden véges S részhalmazának w-színezhető az összehasonlíthatatlansági gráfja . Ezért a de Bruijn–Erdős-tétel alapján kijelenthető , hogy P-nek magának is w-színezhető az összehasonlíthatatlansági gráfja , ezért létezik a kívánt láncfelbontása \ . A tétel nem terjeszthető ki ugyanilyen könnyedséggel arra az esetre , amikor nem csak a halmaz számossága , hanem a részben rendezés szélessége is végtelen . Ebben az esetben a legnagyobb antilánc mérete és a minimális láncfelbontás mérete egymástól nagyon különböző is lehet . Elmondható , hogy bármely κ végtelen kardinális számhoz tartozik olyan ℵ0 szélességű részben rendezés , melynek a minimális láncfelbontásában κ lánc található\. tárgyalja a Dilworth-tétel végtelen analógiáit . A Dilworth-tétel duálisa ( a Mirsky-tétel ) A Dilworth-tétel egy duálisa kimondja , hogy egy részbenrendezés legnagyobb láncának mérete ( ha az véges ) , megegyezik a minimális antilánc-felbontás méretével \ . A bizonyítás sokkal egyszerűbb , mint a Dilworth-tétel esetében : bármely x elemnél tekintsük azokat a láncokat , melyeknek x a legnagyobb eleme , és jelölje N( x ) a legnagyobb ilyen x-maximális lánc méretét . Ekkor minden N−1( i ) halmaz , ami az N egyenlő értékeit tartalmazza , egy antilánc , és ezek az antiláncok a legnagyobb lánccal megegyező darabra bontják fel a részben rendezést . Az összehasonlíthatósági gráfok perfektsége Egy összehasonlíthatósági gráf olyan irányítatlan gráf , amiben egy részbenrendezett halmaz ( poset ) azon elemeinek megfelelő csúcsok vannak összekötve . Így az összehasonlíthatósági gráf klikkjei a részben rendezés egy-egy láncának felel meg , a független csúcshalmazai pedig egy-egy antiláncnak . A részbenrendezés tulajdonságai miatt az összehasonlíthatósági gráfok bármely feszített részgráfja is összehasonlíthatósági gráf . Egy irányítatlan gráf akkor perfekt , ha minden feszített részgráfjának kromatikus száma megegyezik a legnagyobb klikkjének méretével . Az , hogy minden összehasonlíthatósági gráf perfekt , lényegében csak a Mirsky-tétel egy gráfelméleti megfogalmazása \ . A -féle ( gyenge ) perfektgráf-tétel szerint bármely perfekt gráf komplementere is perfekt . Ezért bármely összehasonlíthatósági gráf komplementere is perfekt , ami viszont egyszerűen a Dilworth-tétel gráfelméleti megfogalmazása\ . Más szóval , a perfekt gráfok komplementer-tulajdonsága a Dilworth-tétel alternatív bizonyítását adhatja . Néhány egyedi részbenrendezés szélessége A Bn Boole-háló az n elemű X halmaz – lényegében { 1 , … , n } – hatványhalmaza , melyet a tartalmazás ( részhalmaz ) reláció alapján rendezünk ; jelölésen ] , ⊆ ) . A Sperner-tétel kimondja , hogy Bn egy maximális antiláncának mérete legfeljebb Másképp fogalmazva , az X össze nem hasonlítható részhalmazainak legnagyobb családját az X medián méretű részhalmazainak kiválasztásával kapjuk . A Lubell–Yamamoto–Meshalkin-egyenlőtlenség szintén hatványhalmazok antiláncaival foglalkozik , és alkalmas a Sperner-tétel igazolására . Ha az [ 1 , 2n ] intervallum egészeit oszthatóság alapján rendezzük , a [ n + 1 , 2n ] részintervallum n számosságú antiláncot alkot . Ennek a rendezésnek n láncba való felbontása könnyen elérhető : Az [ 1,2n ] intervallum minden páratlan m egésze láncot alkot az m2i alakú számokkal . Ezért a Dilworth-tétel alapján ennek a részbenrendezésnek a szélessége n . A végtelen sorozatok monoton részsorozataira vonatkozó Erdős–Szekeres-tétel felfogható a Dilworth-tételrendezési dimenziójú részben rendezésekre való alkalmazásaként is \ . Egy antimatroid „ konvex dimenziója” alatt az antimatroid meghatározásához szükséges láncok minimális számát értjük , és a Dilworth-tétel segítségével megmutatható , hogy ez megegyezik a hozzá tartozó részben rendezés szélességével ; emiatt létrehozható a konvex dimenziót polinom időben meghatározó algoritmus \ . Fordítás Jegyzetek . . . . . . . . . . . További információk Equivalence of seven major theorems in combinatorics Kombinatorikai tételek Perfekt gráfok