Dilworth tétele

Dilworth tétele egy kombinatorikus állítás, amely egy extremális tulajdonságot jellemez a pózokra : egy véges posetet fel lehet osztani páronként diszjunkt láncokra , ahol a halmaz [1] legnagyobb antiláncának elemeinek száma (a póz szélességének is nevezik) . $A$ $n$ $n$ $A$

A végtelen pózokra vonatkozó tétel egy változata: Egy póznak akkor és csak akkor van véges szélessége, ha láncokra bontható , de nem kevesebb. $w$ $w$

Robert P. Dilworth ( 1914-1993) amerikai matematikus bizonyította be , akinek fő kutatási területe a rácselmélet volt .

Bizonyítás indukcióval

A pozet méretének indukciós bizonyítása Galvin bizonyításán alapul [2] . $M$

Legyen véges, részben rendezett halmaz. Az állítás triviális, ha üres. Tehát tegyük fel, hogy legalább egy eleme van, és legyen a maximális eleme . $M$ $M$ $M$ $a$ $M$

Az indukciós hipotézis szerint néhány egész szám esetén egy poset lefedhető diszjunkt láncokkal , és legalább egy méretű antilánca van . Egyértelmű, hogy azért . Mert , legyen az a maximális elem , amely a méret antiláncához tartozik és a halmazhoz . Azt állítjuk, hogy ez egy antilánc. Legyen egy méretű antilánc, amely . Rögzítsünk tetszőleges különálló indexeket és . Akkor . Hadd . Akkor definíció szerint . Ebből az következik, hogy mivel . Ha felcseréljük a szerepeket és , akkor kapunk . Ez bizonyítja, hogy ez egy antilánc. $k$ $M':=M\setminus \{a\}$ $k$ $C_{1},\pontok ,C_{k}$ $A_0$ $k$ $A_{0}\cap C_{i}\neq \emptyset$ $i=1,2,\pontok ,k$ $i=1,2,\pontok ,k$ $x_{i}$ $C_{i}$ $k$ $M'$ $A:=\{x_{1},x_{2},\pontok,x_{k}\}$ $A$ $A_{i}$ $k$ $x_{i}$ $én$ $j$ $A_{i}\cap C_{j}\neq \emptyset$ $y\in A_{i}\cap C_{j}$ $y\leq x_{j}$ $x_{j}$ $x_{i}\not \geq x_{j}$ $x_{i}\not \geq y$ $én$ $j$ $x_{j}\not \geq x_{i}$ $A$

Térjünk vissza a . Tegyük fel először, hogy egyesek számára . Legyen egy lánc . Ezután a választásnak köszönhetően nem tartalmaz méretű antiláncot . Az indukciós hipotézisből az következik, hogy lehetséges diszjunkt pályákkal lefedni, mivel egy méretű antilánc . Így igény szerint lehetőség van nem metsző láncokkal való fedésre. $M$ $a\geq x_{i}$ $i\in \{1,2,\pontok ,k\}$ $K$ $\{a\}\cup \{z\in C_{i}:z\leq x_{i}\}$ $x_{i}$ $M\setminus K$ $k$ $M\setminus K$ $k-1$ $A\setminus \{x_{i}\}$ $k-1$ $M\setminus K$ $M$ $k$

Most, ha mindegyikre , akkor egy méretű antilánc (mivel a maximum -ben ) . Így lefedhető láncokkal , ami befejezi a bizonyítást. $a\not \geq x_{i}$ $i\in \{1,2,\pontok ,k\}$ $A\pohár \{a\}$ $k+1$ $M$ $a$ $M$ $M$ $k+1$ $\{a\},C_{1},C_{2},\dots ,C_{k}$

Bizonyítás König tételén keresztül

A kombinatorika egyéb eredményeihez hasonlóan Dilworth tétele is egyenértékű König bipartit gráfok illesztési tételével és néhány más tétellel, köztük Hall esküvői tételével [3] .

Dilworth tételének bizonyítására n elemű S pózra König tételét használva definiálunk egy G = ( U , V , E ) kétrészes gráfot, ahol U = V = S és ( u , v ) egy él G -ben, ha u < v S -re . König tétele szerint van egy illeszkedő M G - ben és C csúcshalmaz G - ben úgy, hogy a gráf minden éle legalább egy C -beli csúcsot tartalmaz, és mindkét halmaznak, M és C , ugyanannyi m eleme van. . Legyen A S azon elemeinek halmaza, amelyek nem felelnek meg egyetlen C -beli csúcsnak sem . Ekkor A -nak legalább n - m eleme van (esetleg több is, ha C a kétoldali gráf mindkét oldalán ugyanannak az elemnek megfelelő csúcsokat tartalmaz). Legyen P a láncok családja, amelyet úgy alkotunk meg, hogy x és y egy láncba kerül, ha M -ben van ( x , y ) él . Ekkor P -nek n - m lánca van. Így szerkesztettünk egy antiláncot és egy láncokra való bontást a halmazban azonos számú elemmel.

König tételének bizonyítására Dilworth tételéből egy kétrészes G = ( U , V , E ) gráfra, G csúcsain parciális rendet alkotunk úgy , hogy u < v -t pontosan akkor állítjuk be, amikor u -t U -ban, v - t V -ben és ott egy él E -ből u - ból v -ben . Dilworth tétele szerint létezik egy antilánc A és egy P láncbontás , mindkettő azonos méretű. De csak a gráf éleinek megfelelő elempárok lehetnek nem triviális láncok részleges sorrendben, így a P -ből származó nemtriviális láncok egyezést alkotnak a gráfban. Az A komplement egy G csúcsborítót képez, amely ugyanannyi elemből áll, mint az illesztésnél.

Ez a kétrészes illesztésekkel való kapcsolat lehetővé teszi bármely rendezett halmaz szélességének kiszámítását polinomiális időben .

Általánosítás korlátlan, részben rendezett halmazokra

A korlátlan, részben rendezett halmazokra vonatkozó Dilworth-tétel kimondja, hogy egy ilyen halmaznak akkor és csak akkor van w szélessége korlátos, ha w láncokra bontható . Tételezzük fel, hogy egy végtelen P póz szélessége w , ami azt jelenti, hogy bármely antilánc legfeljebb véges számú w elemet tartalmaz. P bármely S részhalmazánál a w láncokra bontás (ha létezik) leírható az S összehasonlíthatatlansági gráf (egy olyan gráf, amelynek S elemei csúcsok és élek az összehasonlíthatatlan csúcsokhoz) színezése w szín használatával. Az összehasonlíthatatlansági gráf bármely színezési osztályának láncnak kell lennie. Feltételezve, hogy P szélessége w , a Dilworth-tétel véges esetű változata szerint P bármely véges S részhalmazának w színezése van az összehasonlíthatatlansági gráfban. Így a de Bruijn-Erdős tétel szerint magának P - nek is van w -színe az összehasonlíthatatlansági gráfnak, és ez a kívánt láncokra osztás [4] .

A tétel azonban nem általánosítható olyan könnyen azokra a pózokra, ahol a szélesség nincs korlátos. Ebben az esetben a maximális antiszál mérete és a fedéshez szükséges minimális szálak száma jelentősen eltérhet. Konkrétan, bármely végtelen κ kardinális számhoz létezik egy végtelen, részlegesen rendezett halmaz ℵ 0 szélességgel, amelynek láncokra osztása legalább κ láncot tartalmaz [4] .

1963-ban [5] Dilworth tételéhez hasonló állítást kaptak a korlátlan esetre.

Mirsky tétele

A Dilworth-tétellel kettős tétel, Mirsky tétele azt állítja, hogy a részleges sorrendben a legnagyobb lánc mérete (a végső eset) megegyezik a legkisebb számú antilánccal, amelyre a részleges sorrend felbontható [6 ] . Ennek a tételnek a bizonyítása sokkal egyszerűbb, mint a Dilworth-tételé. Bármely x elemhez vegyünk olyan láncokat, amelyeknél x a maximális elem, és legyen N ( x ) a legnagyobb ezen x -maximum láncok mérete. Ekkor minden N −1 ( i ) halmaz, amely olyan elemekből áll, amelyeknek N értéke megegyezik, antilánc, és egy részlegesen rendezett halmaz antiláncokra való felosztásának mérete megegyezik a legnagyobb lánc méretével.

Az összehasonlíthatósági grafikonok tökéletessége

Az összehasonlíthatósági gráf egy irányítatlan gráf, amelyet részleges sorrendből alakítunk ki úgy, hogy a sorrend minden eleméhez csúcsokat, és bármely két összehasonlítható elemhez éleket hozunk létre. Így az összehasonlíthatósági gráfban egy klikk egy láncnak, egy független halmaz pedig egy antiláncnak felel meg. Az összehasonlíthatósági gráf bármely generált részgráfja maga is egy részleges sorrendből az elemek részhalmazára szűkítve kialakított összehasonlíthatósági gráf.

Egy irányítatlan gráf tökéletes , ha a kromatikus szám minden generált részgráfban megegyezik a legnagyobb klikk méretével. Bármelyik összehasonlíthatósági gráf tökéletes – ez csak Mirsky tétele, a gráfelmélet szempontjából újramondva [7] . Lovas tökéletes gráftétele [ 8] szerint bármely tökéletes gráf komplementere is tökéletes gráf. Így bármely összehasonlíthatósági gráf komplementere tökéletes. Ez lényegében ugyanaz a Dilworth-tétel, amelyet a gráfelmélet szempontjából fogalmaztunk meg [7] . Így a tökéletes gráfok komplementaritási tulajdonsága alternatív bizonyítást jelenthet Dilworth tételére.

Különleges részrendelések szélessége

A B n logikai rács egy n elemből álló X halmaz foka – mondjuk, {1, 2, …, n } –, befogadás szerint rendezve, vagy formálisan (2 [ n ] , ⊆). Sperner tétele kimondja, hogy a maximális antilánc mérete B n -ben nem haladja meg

{\mbox{width}}(B_{n})={n \choose \lfloor {n/2}\rfloor }.

Más szavakkal, az X halmazok összehasonlíthatatlan részhalmazainak legnagyobb családját úgy kapjuk meg, hogy kiválasztjuk X olyan részhalmazait, amelyeknek van átlaga. A Lubell–Yamamoto–Meshalkin egyenlőtlenség egy halmaz hatványainak antiláncaihoz is kapcsolódik, és felhasználható Sperner tételének bizonyítására.

Ha az [1, 2 n ] intervallumban lévő egész számokat oszthatóság szerint rendezzük , az [ n + 1, 2 n ] részintervallum n méretű antiláncot alkot . Ennek a részleges rendnek az n láncra való felbontása könnyen megoldható: minden páratlan m -re [1,2 n ]-ben m 2 i alakú számláncot alkotunk . Így Dilworth tétele szerint ennek a részleges rendnek a szélessége n .

A monoton részszekvenciákról szóló Erdős-Szekeres tétel a Dilworth-tétel kettes részleges dimenziórendekre való alkalmazásaként értelmezhető [9] .

Az antimatroid "konvex dimenziója" az antimatroid meghatározásához szükséges láncok minimális számaként van definiálva, és a Dilworth-tétel felhasználható annak kimutatására, hogy ez egyenlő a kapcsolódó részleges sorrend szélességével. Ez az összefüggés egy idő-lineáris algoritmushoz vezet a konvex dimenzió megtalálására [10] .

Jegyzetek

↑ Marshall Hall Jr. Kombinatorikus elmélet. - "MIR", 1970. - S. 90-94. Archiválva : 2011. október 14. a Wayback Machine -nél
↑ Galvin, 1994 .
↑ Fulkerson, 1956 .
↑ Harzheim 12. , 2005 .
↑ Perles, 1963 .
↑ Mirsky, 1971 .
↑ 1 2 Berge, Chvatal, 1984 .
↑ Lovász, 1972 .
↑ Steele, 1995 .
↑ Edelman, Saks, 1988 .

Irodalom

Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparitás: grafikonok, struktúrák és algoritmusok. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algoritmusok és kombinatorika). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Egbert Harzheim. megrendelt készletek. - New York: Springer, 2005. - V. 7. - S. Tétel 5.6, 60. o. - (Matematika előmenetele (Springer)). - ISBN 0-387-24219-8 .
Claude Berge, Václav Chvatal. Témák a tökéletes grafikonokról. - Elsevier, 1984. - T. 21 . - C. viii . — ISBN 9780444865878 .
Robert P. Dilworth. Felbontási tétel részlegesen rendezett halmazokhoz // Annals of Mathematics . - 1950. - T. 51 , sz. 1 . - S. 161-166 . - doi : 10.2307/1969503 .
Paul H. Edelman, Michael E. Saks. Konvex geometriák kombinatorikus ábrázolása és konvex dimenziója // Rend . - 1988. - V. 5 , sz. 1 . - S. 23-32 . - doi : 10.1007/BF00143895 .
D. R. Fulkerson. Megjegyzés Dilworth részlegesen rendezett halmazokra vonatkozó dekompozíciós tételéhez // Proceedings of the American Mathematical Society . - 1956. - 1. évf. 7 , iss. 4 . - P. 701-702 .
Fred Galvin. A Dilworth-féle láncfelbontási tétel bizonyítása // The American Mathematical Monthly . - 1994. - T. 101 , sz. 4 . - S. 352-353 . - doi : 10.2307/2975628 .
Lovasz László. Normál hipergráfok és a tökéletes gráf sejtés // Diszkrét matematika . - 1972. - T. 2 . - S. 253-267 . - doi : 10.1016/0012-365X(72)90006-4 .
Leon Mirsky. A Dilworth-féle dekompozíciós tétel kettőse // American Mathematical Monthly . - 1971. - T. 78 , sz. 8 . - S. 876-877 . - doi : 10.2307/2316481 . .
Micha A. Perles. Dilworth tételéről a végtelen esetben // Israel Journal of Mathematics. - 1963. - T. 1 . - S. 108-109 . - doi : 10.1007/BF02759806 .
J. Michael Steele. Diszkrét valószínűség és algoritmusok / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. - Springer-Verlag, 1995. - T. 72. - S. 111-131. - (IMA kötetek a matematikából és alkalmazásaiból).
A. V. Spivak, Chains and antichains , Moscow Centre for Continuing Mathematical Education , a látogató matematikai iskola anyagai, 2004.04.7-11.]
Hét fő tétel ekvivalenciája a kombinatorikában
A Dilworth-tétel kettőse (nem elérhető link) . PlanetMath . Letöltve: 2011. június 12. Az eredetiből archiválva : 2007. július 14.. (határozatlan)
Babai László. Előadásjegyzetek: Kombinatorika és valószínűség, 10. előadás: Tökéletes gráfok (2005). Letöltve: 2011. június 12. Az eredetiből archiválva : 2012. május 14.. (határozatlan)
Felsner, S., Raghavan, V. és Spinrad, J. Felismerési algoritmusok kis szélességi sorrendekhez és kis dilworth-szám grafikonjaihoz (1999). Letöltve: 2011. június 12. Az eredetiből archiválva : 2012. május 14.. (határozatlan)
Weisstein, Eric W. Dilworth Lemma (angol) a Wolfram MathWorld webhelyén .