Dilworth-tétel

Sablon:Lektor 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 Sablon:Harvs 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 c_1, c_{2, ...,} c_n ≤ P láncok, hogy P = c₁ $\cup$ c₂ $\cup$ _... $\cup$ c_n, 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: Sablon:Harvs.

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

Tételezzük fel, hogy valamely $k$ egész számra a $P^{\prime }:=P\setminus \{a\}$ részbenrendezett halmaz lefedhető $k$ darab $C_1,\dots ,C_k$ diszjunkt lánccal, és rendelkezik legalább egy $k$ méretű $A_0$ antilánccal. Nyilvánvaló, hogy $A_0\cap C_i\ne \mathrm{\varnothing }$ az $i=1,2,\dots ,k$ értékekre. Az $i=1,2,\dots ,k$ értékekre legyen $x_i$ a $C_i$-beli olyan maximális elem, ami $P^{\prime }$ egy $k$ méretű antiláncához, valamint az $A:=\{x_1,x_2,\dots ,x_k\}$ halmazhoz tartozik. Azt állítjuk, hogy $A$ egy antilánc. Legyen $A_i$ az $x_i$-t tartalmazó, $k$ méretű antilánc. Válasszunk ki 1-1 egymástól eltérő $i$ és $j$ indexet. Ekkor $A_i\cap C_j\ne \mathrm{\varnothing }$. Legyen $y\in A_i\cap C_j$. Ekkor $y\le x_j$, az $x_j$ definíciója alapján. Ebből következik, hogy $x_i\ge ̸x_j$, hiszen $x_i\ge ̸y$. Az $i$ és $j$ szerepét felcserélve, megállapíthatjuk azt is, hogy $x_j\ge ̸x_i$. Ez igazolja, hogy $A$ antilánc.

Térjünk vissza a $P$-hez. Elsőként tegyük fel, hogy $a\ge x_i$ valamely $i\in \{1,2,\dots ,k\}$-re. Legyen $K$ az $\{a\}\cup \{z\in C_i:z\le x_i\}$ lánc. Ekkor az $x_i$ alkalmas megválasztása miatt, $P\setminus K$ nem rendelkezik $k$ méretű antilánccal. Ekkor az indukcióból következik, hogy $P\setminus K$ lefedhető $k-1$ diszjunkt lánccal, hiszen $A\setminus \{x_i\}$ a $P\setminus K$ egy $k-1$ méretű antilánca. Tehát a $P$ a kívánalmaknak megfelelően lefedhető $k$ diszjunkt lánccal. Következőkben, ha minden $i\in \{1,2,\dots ,k\}$-re $a\ge ̸x_i$, akkor $A\cup \{a\}$ a $P$-ben egy $k+1$ méretű antilánc (mivel $a$ maximális $P$-ben). Így $P$ lefedhető a $\{a\},C_1,C_2,\dots ,C_k$ $k+1$ db lánccal, teljessé téve a bizonyítást.

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

A Dilworth-tétel bizonyítása a Kőnig-tétel segítségével: konstruáljunk a részben rendezésből páros gráfot, a láncfelbontás egy párosításnak fog megfelelni

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 Sablon:Harv.

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(kn²) időben detektálható Sablon:Harv.

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 Sablon:Harv.

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 ℵ₀ szélességű részben rendezés, melynek a minimális láncfelbontásában κ lánc található Sablon:Harv.

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

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

Sablon:Fő 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 Sablon:Harv. 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⁻¹(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 Sablon:Harv. A Sablon:Harvtxt-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 Sablon:Harv. 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 B_n 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 B_n egy maximális antiláncának mérete legfeljebb

$\text{szélesség}(B_n)=(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }).$

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 m2ⁱ 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 Sablon:Harv.

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 Sablon:Harv.

Fordítás

• Sablon:Fordítás

Jegyzetek

• Sablon:Citation
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.
• Sablon:Citation.

További információk

• Equivalence of seven major theorems in combinatorics
• Sablon:Citation Sablon:Wayback
• Sablon:Citation
• Sablon:Citation
• Sablon:Mathworld