Dilworthin lause

Dilworthin lause on kombinatorinen lause, joka luonnehtii posettien äärimmäistä ominaisuutta : äärellinen poset voidaan jakaa pareittain hajallaan oleviin ketjuihin , missä on joukon suurimman antiketjun [1] elementtien lukumäärä (kutsutaan myös posetin leveydeksi) . $A$ $n$ $n$ $A$

Lauseen versio äärettömille asetuksille: Posetilla on rajallinen leveys , jos ja vain jos se voidaan jakaa ketjuihin, mutta ei vähemmän. $w$ $w$

Sen todisti amerikkalainen matemaatikko Robert P. Dilworth ( 1914-1993), jonka pääasiallinen tutkimusalue oli hilateoria .

Todistus induktiolla

Induktiotodistus posetin koosta perustuu Galvinin todistukseen [2] . $M$

Olkoon äärellinen osittain järjestetty joukko. Lauseke on triviaali, jos se on tyhjä. Joten oletetaan, että on vähintään yksi elementti, ja anna olla suurin osa . $M$ $M$ $M$ $a$ $M$

Induktiohypoteesin mukaan jollekin kokonaisluvulle poset voidaan peittää epäyhtenäisillä ketjuilla ja sillä on vähintään yksi antiketju , jonka koko on . On selvää, että varten . Sillä , anna olla suurin elementti , joka kuuluu koon antiketjuun ja joukkoon . Väitämme , että se on antiketju. Antaa olla antichain koon sisältävät . Korjataan mielivaltaiset erilliset indeksit ja . Sitten . Anna . Siis määritelmän mukaan . Tästä seuraa, että koska . Jos vaihdamme rooleja ja saamme . Tämä todistaa, että se on antiketju. $k$ $M':=M\setmiinus \{a\}$ $k$ $C_{1},\pisteet ,C_{k}$ $A_0$ $k$ $A_{0}\cap C_{i}\neq \emptyset$ $i=1,2,\pisteet ,k$ $i=1,2,\pisteet ,k$ $x_{i}$ $C_{i}$ $k$ $M'$ $A:=\{x_{1},x_{2},\dots ,x_{k}\}$ $A$ $A_{i}$ $k$ $x_{i}$ $i$ $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$ $i$ $j$ $x_{j}\not \geq x_{i}$ $A$

Palataan asiaan . Oletetaan ensin, että joillekin . Olkoon ketju . Sitten valinnan vuoksi se ei sisällä kokoa . Induktiohypoteesista seuraa, että on mahdollista peittää epäyhtenäisillä poluilla, koska on antiketju, jonka koko on . Siten on mahdollista peittää ei-leikkautuvilla ketjuilla tarpeen mukaan. $M$ $a\geq x_{i}$ $i\in \{1,2,\pisteet ,k\}$ $K$ $\{a\}\cup \{z\in C_{i}:z\leq x_{i}\}$ $x_{i}$ $M\setminus K$ $k$ $M\setminus K$ $k-1$ $A\setmiinus \{x_{i}\}$ $k-1$ $M\setminus K$ $M$ $k$

Nyt, jos kunkin , sitten on antichain koon ( koska on suurin vuonna ). Siten voidaan kattaa ketjuilla , mikä täydentää todisteen. $a\not \geq x_{i}$ $i\in \{1,2,\pisteet ,k\}$ $A\kuppi \{a\}$ $k+1$ $M$ $a$ $M$ $M$ $k+1$ $\{a\},C_{1},C_{2},\dots ,C_{k}$

Todistus Königin lauseen kautta

Kuten muutkin kombinatoriikan tulokset, Dilworthin lause vastaa Königin lausetta kaksiosaisten graafien sovituksista ja joitain muita lauseita, mukaan lukien Hallin häälause [3] .

Todistaaksemme Dilworthin lauseen posetille S , jossa on n elementtiä, määritämme Königin lauseen avulla kaksiosaisen graafin G = ( U , V , E ), jossa U = V = S ja ( u , v ) on G :n reuna, jos u < v - S . Königin lauseen mukaan G :ssä on sopiva M ja G :ssä joukko pisteitä C siten , että jokainen graafin reuna sisältää vähintään yhden kärjen C :stä ja molemmissa joukoissa M ja C on sama määrä alkioita m . Olkoon A joukko S :n alkioita, jotka eivät vastaa yhtään C :n kärkeä . Tällöin A :lla on vähintään n - m elementtiä (mahdollisesti enemmän, jos C sisältää samaa alkiota vastaavia pisteitä kaksiosaisen graafin molemmilla puolilla). Olkoon P ketjujen perhe, joka muodostetaan sisällyttämällä x ja y yhteen ketjuun, kun M :ssä on reuna ( x , y ) . Silloin P :llä on n - m ketjua. Näin ollen olemme rakentaneet antiketjun ja hajotuksen ketjuiksi, joissa on sama määrä elementtejä joukossa.

Todistaaksemme Königin lauseen Dilworthin lauseesta kaksiosaiselle graafille G = ( U , V , E ) muodostamme osittaisjärjestyksen G :n huipuille asettamalla u < v tarkalleen, kun u sisältyy U :een , v sisältyy V :hen ja on reuna E :stä u :sta v :ssä . Dilworthin lauseen mukaan on olemassa antiketju A ja ketjun hajoaminen P , molemmat joukot ovat samankokoisia. Mutta vain elementiparit, jotka vastaavat graafin reunoja, voivat olla ei-triviaaleja ketjuja osittaisessa järjestyksessä, joten ei-triviaalit ketjut P :stä muodostavat graafissa yhteensovituksen. Komplementti A muodostaa kärjen kannen G , jossa on sama määrä elementtejä kuin sovituksessa.

Tämä yhteys bipartite matchings mahdollistaa minkä tahansa järjestetyn joukon leveyden laskemisen polynomiajassa .

Yleistys rajoittamattomiin osittain järjestettyihin ryhmiin

Dilworthin lause rajoittamattomille osittain järjestetyille joukoille sanoo, että tällaisella joukolla on rajoitettu leveys w silloin ja vain, jos se voidaan hajottaa w - ketjuiksi. Oletetaan, että äärettömällä posetilla P on leveys w , mikä tarkoittaa, että mikä tahansa antiketju sisältää enintään äärellisen määrän w alkioita. Minkä tahansa P :n osajoukon S jakaminen w - ketjuihin (jos sellainen on) voidaan kuvata verrattomuusgraafin S (graafin, jossa on S :n elementit kärkeinä ja verrattomien kärkien reunoja) värjäytymisenä käyttämällä w - värejä. Vertailemattomuuden graafin minkä tahansa väritysluokan on oltava ketju. Olettaen, että P :llä on leveys w , Dilworthin lauseen äärellisen tapauksen versiolla millä tahansa P:n äärellisellä osajoukolla S on verrattomuusgraafin w -väri . Siten de Bruijn-Erdősin lauseen mukaan P :llä itsellään on myös vertailukelpoisuusgraafin w -väritys, ja tämä on haluttu jako ketjuihin [4] .

Lause ei kuitenkaan yleisty niin helposti poseteihin, joissa leveyttä ei ole rajoitettu. Tässä tapauksessa suurimman antisäikeen koko ja peittämiseen vaadittavien säikeiden vähimmäismäärä voivat vaihdella merkittävästi. Erityisesti mille tahansa äärettömälle kardinaaliluvulle κ on olemassa ääretön osittain järjestetty joukko, jonka leveys on ℵ 0 ja jonka ketjujako sisältää vähintään κ ketjua [4] .

Vuonna 1963 [5] saatiin rajoittamattomalle tapaukselle Dilworthin lauseen kaltainen väite.

Mirskyn lause

Lause, joka on kaksoislause Dilworthin lauseen kanssa, Mirskyn teoreema , väittää, että suurimman ketjun koko osittaisessa järjestyksessä (lopullinen tapaus) on yhtä suuri kuin pienin määrä antiketjuja, joihin osajärjestys voidaan hajottaa [6 ] . Tämän lauseen todistus on paljon yksinkertaisempi kuin Dilworthin lauseen. Otetaan mille tahansa elementille x ketjut, joiden maksimielementti on x , ja olkoon N ( x ) suurimman näistä x -max- ketjuista. Tällöin jokainen joukko N −1 ( i ), joka koostuu alkioista, joilla on samat N:n arvot, on antiketju, ja tämän osittain järjestetyn joukon antiketjuiksi jaon koko on yhtä suuri kuin suurimman ketjun koko.

Vertailukaavioiden täydellisyys

Vertailugraafi on suuntaamaton graafi, joka on muodostettu osittaisesta järjestyksestä luomalla pisteet jokaiselle järjestyksen elementille ja reunat mille tahansa kahdelle vertailukelpoiselle elementille. Siten vertailukelpoisuuskaavion klikki vastaa ketjua ja riippumaton joukko vastaa antiketjua. Mikä tahansa vertailukelpoisuusgraafin luotu osagraafi on itsessään vertailukelpoisuuskaavio, joka on muodostettu osittaisesta järjestyksestä kaventamalla elementtien osajoukkoon.

Suuntaamaton graafi on täydellinen , jos kromaattinen luku jokaisessa generoidussa aligraafissa on yhtä suuri kuin suurimman klikkin koko. Mikä tahansa vertailukelpoisuusgraafi on täydellinen - tämä on vain Mirskyn lause, joka on kerrottu uudelleen graafiteorian kannalta [7] . Lovasin täydellisen graafin lauseen [8] mukaan minkä tahansa täydellisen graafin komplementti on myös täydellinen graafi. Siten minkä tahansa vertailtavuuden graafin komplementti on täydellinen. Tämä on pohjimmiltaan sama graafiteorian kannalta muotoiltu Dilworthin lause [7] . Siten täydellisten graafien komplementaarisuusominaisuus voi tarjota vaihtoehtoisen todisteen Dilworthin lauseelle.

Erikoisosatilausten leveys

Boolen hila B n on joukon X aste, jossa on n alkiota — esimerkiksi {1, 2, …, n } — inkluusiojärjestyksessä tai muodollisesti (2 [ n ] , ⊆). Spernerin lause sanoo, että B n :n maksimiantiketjun koko ei ylitä

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

Toisin sanoen joukkojen X suurin verrattomuusosajoukkojen perhe saadaan valitsemalla X:n osajoukot, joilla on keskiarvo. Lubell–Yamamoto–Meshalkin-epäyhtälö liittyy myös joukon potenssien antiketjuihin ja sitä voidaan käyttää Spernerin lauseen todistamiseen.

Jos järjestät välin [1, 2 n ] kokonaisluvut jaollisuudella , osaväli [ n + 1, 2 n ] muodostaa antiketjun, jonka koko on n . Tämän osittaisen järjestyksen hajottaminen n ketjuun on helppo saada: jokaiselle parittomille m :lle [1,2 n ] muodostamme lukuketjun muotoa m 2 i . Siten Dilworthin lauseen mukaan tämän osittaisjärjestyksen leveys on n .

Erdős-Szekeres-lause monotonisista osasarjoista voidaan tulkita Dilworth-lauseen sovellukseksi osittaisille ulottuvuuksille kaksi [9] .

Antimatroidin "kupera ulottuvuus" määritellään antimatroidin määrittämiseen tarvittavien ketjujen vähimmäismääräksi, ja Dilworthin lausetta voidaan käyttää osoittamaan, että se on yhtä suuri kuin siihen liittyvän osittaisen järjestyksen leveys. Tämä suhde johtaa aikalineaariseen algoritmiin kuperan ulottuvuuden löytämiseksi [10] .

Muistiinpanot

↑ Marshall Hall Jr. Kombinatorinen teoria. - "MIR", 1970. - S. 90-94. Arkistoitu 14. lokakuuta 2011 Wayback Machinessa
↑ Galvin, 1994 .
↑ Fulkerson, 1956 .
↑ 12 Harzheim , 2005 .
↑ Perles, 1963 .
↑ Mirsky, 1971 .
↑ 1 2 Berge, Chvatal, 1984 .
↑ Lovász, 1972 .
↑ Steele, 1995 .
↑ Edelman, Saks, 1988 .

Kirjallisuus

Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: kaaviot, rakenteet ja algoritmit. - Heidelberg: Springer, 2012. - T. 28. - S. 42. - (Algoritmit ja kombinatoriikka). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Egbert Harzheim. tilatut setit. - New York: Springer, 2005. - V. 7. - S. Lause 5.6, s. 60. - (Matematiikan edistyminen (Springer)). - ISBN 0-387-24219-8 .
Claude Berge, Václav Chvatal. Täydellisten kaavioiden aiheita. - Elsevier, 1984. - T. 21 . - C. viii . — ISBN 9780444865878 .
Robert P. Dilworth. Hajotuslause osittain järjestetyille joukoille // Matematiikan Annals . - 1950. - T. 51 , no. 1 . - S. 161-166 . - doi : 10.2307/1969503 .
Paul H. Edelman, Michael E. Saks. Konveksien geometrioiden kombinatorinen esitys ja kupera ulottuvuus // Järjestys . - 1988. - V. 5 , no. 1 . - S. 23-32 . - doi : 10.1007/BF00143895 .
D. R. Fulkerson. Huomautus Dilworthin hajottelulauseesta osittain järjestetyille joukoille // Proceedings of the American Mathematical Society . - 1956. - Voi. 7 , iss. 4 . - s. 701-702 .
Fred Galvin. Todiste Dilworthin ketjuhajotuslauseesta // The American Mathematical Monthly . - 1994. - T. 101 , no. 4 . - S. 352-353 . - doi : 10.2307/2975628 .
László Lovasz. Normaalit hypergraafit ja täydellinen graafi-oletus // Diskreetti matematiikka . - 1972. - T. 2 . - S. 253-267 . - doi : 10.1016/0012-365X(72)90006-4 .
Leon Mirsky. Dilworthin hajoamislauseen kaksoiskappale // American Mathematical Monthly . - 1971. - T. 78 , no. 8 . - S. 876-877 . - doi : 10.2307/2316481 . .
Micha A. Perles. Dilworthin lauseesta äärettömässä tapauksessa // Israel Journal of Mathematics. - 1963. - T. 1 . - S. 108-109 . - doi : 10.1007/BF02759806 .
J. Michael Steele. Diskreetti todennäköisyys ja algoritmit / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. - Springer-Verlag, 1995. - T. 72. - S. 111-131. - (IMA-määrät matematiikassa ja sen sovelluksissa).
A. V. Spivak, Chains and antichains , Moskovan matematiikan jatkokoulutuskeskus , vierailevan matemaattisen koulun materiaalit, 7-11.04.2004.]
Seitsemän päälauseen vastaavuus kombinatoriikassa
Dilworthin lauseen kaksoiskappale (linkki ei saatavilla) . PlanetMath . Haettu 12. kesäkuuta 2011. Arkistoitu alkuperäisestä 14. heinäkuuta 2007. (määrätön)
Babai, László. Kombinatoriikka ja todennäköisyysluvut, Luento 10: Perfect Graphs (2005). Haettu 12. kesäkuuta 2011. Arkistoitu alkuperäisestä 14. toukokuuta 2012. (määrätön)
Felsner, S., Raghavan, V. ja Spinrad, J. Pienen leveyden tilausten tunnistusalgoritmit ja pienen Dilworth- luvun kuvaajat (1999). Haettu 12. kesäkuuta 2011. Arkistoitu alkuperäisestä 14. toukokuuta 2012. (määrätön)
Weisstein, Eric W. Dilworth's Lemma (englanniksi) Wolfram MathWorld -verkkosivustolla .