Dilworth-tétel

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját!

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 Robert P. Dilworth (1950) 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₁ ${\displaystyle \cup }$ c₂ ${\displaystyle \cup }$ _... ${\displaystyle \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.

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

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

Tételezzük fel, hogy valamely ${\displaystyle k}$ egész számra a ${\displaystyle P':=P\setminus \{a\}}$ részbenrendezett halmaz lefedhető ${\displaystyle k}$ darab ${\displaystyle C_{1},\dots ,C_{k}}$ diszjunkt lánccal, és rendelkezik legalább egy ${\displaystyle k}$ méretű ${\displaystyle A_{0}}$ antilánccal. Nyilvánvaló, hogy ${\displaystyle A_{0}\cap C_{i}\neq \emptyset }$ az ${\displaystyle i=1,2,\dots ,k}$ értékekre. Az ${\displaystyle i=1,2,\dots ,k}$ értékekre legyen ${\displaystyle x_{i}}$ a ${\displaystyle C_{i}}$-beli olyan maximális elem, ami ${\displaystyle P'}$ egy ${\displaystyle k}$ méretű antiláncához, valamint az ${\displaystyle A:=\{x_{1},x_{2},\dots ,x_{k}\}}$ halmazhoz tartozik. Azt állítjuk, hogy ${\displaystyle A}$ egy antilánc. Legyen ${\displaystyle A_{i}}$ az ${\displaystyle x_{i}}$-t tartalmazó, ${\displaystyle k}$ méretű antilánc. Válasszunk ki 1-1 egymástól eltérő ${\displaystyle i}$ és ${\displaystyle j}$ indexet. Ekkor ${\displaystyle A_{i}\cap C_{j}\neq \emptyset }$. Legyen ${\displaystyle y\in A_{i}\cap C_{j}}$. Ekkor ${\displaystyle y\leq x_{j}}$, az ${\displaystyle x_{j}}$ definíciója alapján. Ebből következik, hogy ${\displaystyle x_{i}\not \geq x_{j}}$, hiszen ${\displaystyle x_{i}\not \geq y}$. Az ${\displaystyle i}$ és ${\displaystyle j}$ szerepét felcserélve, megállapíthatjuk azt is, hogy ${\displaystyle x_{j}\not \geq x_{i}}$. Ez igazolja, hogy ${\displaystyle A}$ antilánc.

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

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 (Fulkerson 1956).

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ó (Felsner, Raghavan & Spinrad 2003).

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 (Harzheim 2005).

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ó (Harzheim 2005).

(Perles 1963) tárgyalja a Dilworth-tétel végtelen analógiáit.

Bővebben: 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 (Mirsky 1971). 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.

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 (Berge & Chvátal 1984). A (Lovász 1972)-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 (Berge & Chvátal 1984). Más szóval, a perfekt gráfok komplementer-tulajdonsága a Dilworth-tétel alternatív bizonyítását adhatja.

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

${\displaystyle {\mbox{szélesség}}(B_{n})={n \choose \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 (Steele 1995).

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 (Edelman & Saks 1988).

• Ez a szócikk részben vagy egészben a Dilworth's theorem 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.

• Berge, Claude & Chvátal, Václav (1984), Topics on Perfect Graphs, vol. 21, Annals of Discrete Mathematics, Elsevier, p. viii, ISBN 978-0-444-86587-8
• Dilworth, Robert P. (1950), "A Decomposition Theorem for Partially Ordered Sets", Annals of Mathematics 51 (1): 161–166, DOI 10.2307/1969503.
• Edelman, Paul H. & Saks, Michael E. (1988), "Combinatorial representation and convex dimension of convex geometries", Order 5 (1): 23–32, DOI 10.1007/BF00143895.
• Felsner, Stefan; Raghavan, Vijay & Spinrad, Jeremy (2003), "Recognition algorithms for orders of small width and graphs of small Dilworth number", Order 20 (4): 351–364 (2004), DOI 10.1023/B:ORDE.0000034609.99940.fb.
• Fulkerson, D. R. (1956), "Note on Dilworth’s decomposition theorem for partially ordered sets", Proceedings of the American Mathematical Society 7 (4): 701–702, DOI 10.2307/2033375.
• Galvin, Fred (1994), "A proof of Dilworth's chain decomposition theorem", The American Mathematical Monthly 101 (4): 352–353, DOI 10.2307/2975628.
• Harzheim, Egbert (2005), Ordered sets, vol. 7, Advances in Mathematics (Springer), New York: Springer, Theorem 5.6, p. 60, ISBN 0-387-24219-8, <https://books.google.com/books?id=FYV6tGm3NzgC&pg=PA59>.
• Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics 2 (3): 253–267, DOI 10.1016/0012-365X(72)90006-4.
• Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly 78 (8): 876–877, DOI 10.2307/2316481.
• Nešetřil, Jaroslav & Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, vol. 28, Algorithms and Combinatorics, Heidelberg: Springer, p. 42, ISBN 978-3-642-27874-7, DOI 10.1007/978-3-642-27875-4.
• Perles, Micha A. (1963), "On Dilworth's theorem in the infinite case", Israel Journal of Mathematics 1 (2): 108–109, DOI 10.1007/BF02759806.
• Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi & Spencer, Joel et al., Discrete Probability and Algorithms, vol. 72, IMA Volumes in Mathematics and its Applications, Springer-Verlag, pp. 111–131, <http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf>.

• Equivalence of seven major theorems in combinatorics
• Dual of Dilworth's Theorem, <http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html> Archiválva 2007. július 14-i dátummal a Wayback Machine-ben
• Babai, László (2005), Lecture notes in Combinatorics and Probability, Lecture 10: Perfect Graphs, <http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf>
• Felsner, S.; Raghavan, V. & Spinrad, J. (1999), Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number, <http://www.inf.fu-berlin.de/inst/pubs/tr-b-99-05.abstract.html>
• Weisstein, Eric W.: Dilworth's Lemma (angol nyelven). Wolfram MathWorld