Dilworths teorem

Dilworths teorem är ett kombinatoriskt uttalande som kännetecknar en extremal egenskap för posetter : en finit poset kan delas upp i parvis disjunkta kedjor , där är antalet element i den största antikedjan i mängden [1] (även kallad posets bredd) . $A$ $n$ $n$ $A$

En version av satsen för oändliga posetter: En poset har ändlig bredd om och bara om den kan brytas ner i kedjor, men inte mindre. $w$ $w$

Det bevisades av den amerikanske matematikern Robert P. Dilworth ( 1914-1993), vars huvudområde för forskning var gitterteori .

Bevis genom induktion

Beviset genom induktion på storleken på en poset är baserat på Galvins bevis [2] . $M$

Låt vara en ändlig delvis ordnad uppsättning. Uttalandet är trivialt om det är tomt. Så anta att det har minst ett element, och låt vara det maximala elementet av . $M$ $M$ $M$ $a$ $M$

Enligt induktionshypotesen, för något heltal , kan en poset täckas av disjunkta kedjor och har minst en antikedja av storlek . Det är klart att för . För , låt vara det maximala elementet i , som hör till antikedjan av storlek i och till uppsättningen . Vi hävdar att det är en antikedja. Låt vara en antikedja av storlek som innehåller . Låt oss fixa godtyckliga distinkta index och . Sedan . Låt . Då per definition . Av detta följer att , sedan . Om vi byter roller och , får vi . Detta bevisar att det är en antikedja. $k$ $M':=M\setminus \{a\}$ $k$ $C_{1},\dots ,C_{k}$ $A_0$ $k$ $A_{0}\cap C_{i}\neq \emptyset$ $i=1,2,\prickar ,k$ $i=1,2,\prickar ,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}\inte \geq y$ $i$ $j$ $x_{j}\not \geq x_{i}$ $A$

Låt oss gå tillbaka till . Anta först att för vissa . Låt vara en kedja . Då, på grund av valet , innehåller inte en antikedja av storlek . Det följer av induktionshypotesen att det är möjligt att täcka med disjunkta banor, eftersom är en antikedja av storlek i . Således är det möjligt att täcka med icke-korsande kedjor, efter behov. $M$ $a\geq x_{i}$ $i\in \{1,2,\dots ,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$

Nu, om för varje , då är en antikedja av storlek i (eftersom är maximum i ). Således kan täckas av kedjor , vilket kompletterar beviset. $a\not \geq x_{i}$ $i\in \{1,2,\dots ,k\}$ $A\kopp \{a\}$ $k+1$ $M$ $a$ $M$ $M$ $k+1$ $\{a\},C_{1},C_{2},\dots ,C_{k}$

Bevis via Königs sats

Liksom andra resultat av kombinatorik är Dilworths sats likvärdig med Königs sats om matchningar på tvådelade grafer och några andra satser, inklusive Halls bröllopssats [3] .

För att bevisa Dilworths sats för en sats S med n element, med hjälp av Königs sats, definierar vi en tvådelad graf G = ( U , V , E ) där U = V = S och ( u , v ) är en kant i G om u < v till S. _ Enligt Königs sats finns det en matchande M i G , och en uppsättning hörn C i G , så att varje kant från grafen innehåller minst en vertex från C och båda mängderna, M och C , har samma antal element m . Låt A vara mängden element i S som inte motsvarar någon vertex i C . Då har A minst n - m element (möjligen fler om C innehåller hörn som motsvarar samma element på båda sidor av den tvådelade grafen). Låt P vara familjen av kedjor som bildas genom att inkludera x och y i en kedja när det finns en kant ( x , y ) i M. Då har P n - m kedjor. Således har vi konstruerat en antikedja och en nedbrytning till kedjor med samma antal element i uppsättningen.

För att bevisa Königs sats från Dilworths sats för en tvådelad graf G = ( U , V , E ) bildar vi en partiell ordning på G :s hörn genom att sätta u < v exakt när u ingår i U , v finns i V och där är en kant från E från u i v . Enligt Dilworths teorem finns det en antikedja A och en kedjesönderdelning P , båda uppsättningar av samma storlek. Men endast par av element som motsvarar grafens kanter kan vara icke-triviala kedjor i partiell ordning, så icke-triviala kedjor från P bildar en matchning i grafen. Komplement A bildar ett vertextäcke G med samma antal element som i matchningen.

Denna koppling med tvådelade matchningar gör det möjligt att beräkna bredden på vilken som helst ordnad mängd i polynomtid .

Generalisering till ogränsade partiellt ordnade uppsättningar

Dilworths teorem för obegränsade partiellt ordnade mängder säger att en sådan mängd har begränsad bredd w om och endast om den kan dekomponeras i w -kedjor. Antag att en oändlig poset P har bredd w , vilket betyder att vilken antikedja som helst innehåller högst ett ändligt antal w element. För varje delmängd S av P kan nedbrytningen till w -kedjor (om den finns) beskrivas som en färgning av oförlikbarhetsgrafen S (en graf som har element av S som hörn och kanter för ojämförliga hörn) med w- färger. Vilken färgklass som helst i en oförlikbarhetsgraf måste vara en kedja. Om vi antar att P har bredd w , enligt den finita kasusversionen av Dilworths sats, har vilken ändlig delmängd S av P som helst en w -färgning av oförjämförbarhetsgrafen. Sålunda, enligt de Bruijn-Erdős sats , har P i sig också en w -färgning av injämförbarhetsgrafen, och detta är den önskade uppdelningen i kedjor [4] .

Men satsen generaliserar inte så lätt till fallet med posetter där bredden inte är begränsad. I det här fallet kan storleken på den maximala antisträngen och det minsta antalet trådar som krävs för täckning skilja sig betydligt. Speciellt, för vilket oändligt kardinaltal κ som helst, finns det en oändlig partiellt ordnad mängd med bredd ℵ 0 vars uppdelning i kedjor har minst κ-kedjor [4] .

År 1963 [5] erhölls ett uttalande som liknar Dilworths teorem för det obegränsade fallet.

Mirskys teorem

Teoremet som är dubbelt till Dilworths sats, Mirskys sats , hävdar att storleken på den största kedjan i en partiell ordning (det sista fallet) är lika med det minsta antalet antikedjor i vilka den partiella ordningen kan dekomponeras [6 ] . Beviset för denna sats är mycket enklare än Dilworths sats. För vilket element x som helst , ta kedjor som har x som maxelement och låt N ( x ) vara storleken på den största av dessa x -maximumkedjor . Då är varje uppsättning N −1 ( i ) som består av element som har samma värden på N en antikedja, och storleken på denna uppdelning av en delvis ordnad uppsättning i antikedjor är lika med storleken på den största kedjan.

Perfektion av jämförbarhetsgrafer

En jämförbarhetsgraf är en oriktad graf som bildas från en partiell ordning genom att skapa hörn för varje element i ordningen och kanter för två jämförbara element. Således motsvarar en klick i jämförbarhetsgrafen en kedja och en oberoende uppsättning motsvarar en antikedja. Varje genererad subgraf av en jämförbarhetsgraf är i sig en jämförbarhetsgraf som bildas från en partiell ordning genom att begränsas till en delmängd av element.

En oriktad graf är perfekt om det kromatiska talet i varje genererad subgraf är lika med storleken på den största klicken. Vilken jämförbarhetsgraf som helst är perfekt - detta är bara Mirskys teorem, återberättad i termer av grafteorin [7] . Enligt Lovas perfekta grafsats [8] är komplementet till varje perfekt graf också en perfekt graf. Således är komplementet till alla jämförbarhetsdiagram perfekt. Detta är i huvudsak samma Dilworths teorem formulerad i termer av grafteorin [7] . Således kan komplementaritetsegenskapen hos perfekta grafer ge ett alternativt bevis för Dilworths sats.

Bredd på särskilda delordrar

Det booleska gittret B n är graden av en uppsättning X av n element – säg {1, 2, …, n } – ordnade efter inkludering, eller formellt (2 [ n ] , ⊆). Sperners teorem säger att den maximala antikedjan i B n har en storlek som inte överstiger

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

Med andra ord erhålls den största familjen av oförlikbarhetsdelmängder av mängder X genom att välja delmängder av X som har ett medelvärde. Lubell–Yamamoto–Meshalkin-ojämlikheten är också relaterad till antikedjor i potenser av en mängd och kan användas för att bevisa Sperners teorem.

Om du ordnar heltalen i intervallet [1, 2 n ] efter delbarhet , bildar delintervallet [ n + 1, 2 n ] en antikedja av storlek n . Nedbrytningen av denna delordning i n kedjor är lätt att få: för varje udda m i [1,2 n ] bildar vi en talkedja av formen m 2 i . Således, enligt Dilworths sats, är bredden på denna partiella ordning n .

Erdős-Szekeres sats om monotona delsekvenser kan tolkas som en tillämpning av Dilworths sats på partiella dimensionsordningar två [9] .

Den "konvexa dimensionen" av en antimatroid definieras som det minsta antalet kedjor som behövs för att definiera en antimatroid, och Dilworths sats kan användas för att visa att den är lika med bredden på den tillhörande partiella ordningen. Detta förhållande leder till en tidslinjär algoritm för att hitta en konvex dimension [10] .

Anteckningar

↑ Marshall Hall Jr. Kombinatorisk teori. - "MIR", 1970. - S. 90-94. Arkiverad 14 oktober 2011 på Wayback Machine
↑ Galvin, 1994 .
↑ Fulkerson, 1956 .
↑ 12 Harzheim , 2005 .
↑ Perles, 1963 .
↑ Mirsky, 1971 .
↑ 1 2 Berge, Chvatal, 1984 .
↑ Lovász, 1972 .
↑ Steele, 1995 .
↑ Edelman, Saks, 1988 .

Litteratur

Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparity: Grafer, strukturer och algoritmer. - Heidelberg: Springer, 2012. - T. 28. - P. 42. - (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Egbert Harzheim. beställda set. - New York: Springer, 2005. - V. 7. - S. Theorem 5.6, s.60. - (Framsteg i matematik (Springer)). - ISBN 0-387-24219-8 .
Claude Berge, Václav Chvatal. Ämnen om Perfect Graphs. - Elsevier, 1984. - T. 21 . - C. viii . — ISBN 9780444865878 .
Robert P. Dilworth. En nedbrytningssats för partiellt ordnade mängder // Annals of Mathematics . - 1950. - T. 51 , nr. 1 . - S. 161-166 . - doi : 10.2307/1969503 .
Paul H. Edelman, Michael E. Saks. Kombinatorisk representation och konvex dimension av konvexa geometrier // Ordning . - 1988. - V. 5 , nr. 1 . - S. 23-32 . - doi : 10.1007/BF00143895 .
D. R. Fulkerson. Anmärkning om Dilworths nedbrytningssats för delvis ordnade uppsättningar // Proceedings of the American Mathematical Society . - 1956. - Vol. 7 , iss. 4 . - s. 701-702 .
Fred Galvin. Ett bevis på Dilworths kedjenedbrytningssats // The American Mathematical Monthly . - 1994. - T. 101 , nr. 4 . - S. 352-353 . - doi : 10.2307/2975628 .
Laszlo Lovasz. Normala hypergrafer och den perfekta grafförmodan // Diskret matematik . - 1972. - T. 2 . - S. 253-267 . - doi : 10.1016/0012-365X(72)90006-4 .
Leon Mirsky. En dual av Dilworths nedbrytningssats // American Mathematical Monthly . - 1971. - T. 78 , nr. 8 . - S. 876-877 . - doi : 10.2307/2316481 . .
Micha A. Perles. Om Dilworths sats i det oändliga fallet // Israel Journal of Mathematics. - 1963. - T. 1 . - S. 108-109 . - doi : 10.1007/BF02759806 .
J. Michael Steele. Diskret sannolikhet och algoritmer / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. - Springer-Verlag, 1995. - T. 72. - S. 111-131. - (IMA volymer i matematik och dess tillämpningar).
A. V. Spivak, Chains and antichains , Moskvas centrum för fortsatt matematisk utbildning , material från den besökande matematikskolan, 7-11.04.2004.]
Ekvivalens av sju stora satser i kombinatorik
Dual of Dilworth's Theorem (inte tillgänglig länk) . PlanetMath . Hämtad 12 juni 2011. Arkiverad från originalet 14 juli 2007. (obestämd)
Babai, Laszlo. Föreläsningsanteckningar i kombinatorik och sannolikhet, föreläsning 10: Perfekta grafer (2005). Hämtad 12 juni 2011. Arkiverad från originalet 14 maj 2012. (obestämd)
Felsner, S., Raghavan, V. och Spinrad, J. Erkännandealgoritmer för beställningar av liten bredd och grafer av små Dilworth-tal (1999). Hämtad 12 juni 2011. Arkiverad från originalet 14 maj 2012. (obestämd)
Weisstein, Eric W. Dilworths Lemma (engelska) på Wolfram MathWorld- webbplatsen .