Dilworths teorem

"Kedjenedbrytning" omdirigerar hit. För sönderdelning av vägen, se Nedbrytning av tung väg .

Inom matematik , inom områdena ordningsteori och kombinatorik , kännetecknar Dilworths sats bredden på alla ändliga delvis ordnade uppsättningar i termer av en uppdelning av beställningen i ett minsta antal kedjor . Den är uppkallad efter matematikern Robert P. Dilworth ( 1950 ).

En antikedja i en partiellt ordnad uppsättning är en uppsättning element varav två är jämförbara med varandra, och en kedja är en uppsättning element varav två är jämförbara. En kedjesönderdelning är en uppdelning av beståndsdelarna i ordningen i osammanhängande kedjor. Dilworths teorem säger att, i varje ändlig partiellt ordnad mängd, har den största antikedjan samma storlek som den minsta kedjenedbrytningen. Här är storleken på antikedjan dess antal element, och storleken på kedjenedbrytningen är dess antal kedjor. Bredden på den partiella ordningen definieras som den gemensamma storleken på antikedjan och kedjenedbrytningen.

En version av satsen för oändliga partiellt ordnade mängder säger att när det finns en sönderdelning i ändligt många kedjor, eller när det finns en ändlig övre gräns för storleken på en antikedja, storleken på den största antikedjan och den minsta kedjenedbrytningen är återigen lika.

Induktivt bevis

Följande bevis genom induktion på storleken på den delvis ordnade uppsättningen $P$ är baserat på det från Galvin ( 1994 ).

Låt $P$ vara en finit partiellt ordnad mängd. Satsen gäller trivialt om $P$ är tom. Så, antag att $P$ har minst ett element, och låt $a$ vara ett maximalt element av $P$ .

Genom induktion antar vi att för något heltal ${\displaystyle k} kan$ den delvis ordnade mängden $P':=P\setminus \{a\}$ täckas av ${ \displaystyle k}$ disjunkta kedjor $C_{1},\dots ,C_{k}$ och har minst en antikedja $A_{0}$ av storleken $k$ . Helt klart, $A_{0}\cap C_{i}\neq \emptyset$ för $i=1,2,\dots ,k$ . För $i=1,2,\dots ,k$ , låt $x_{i}$ vara det maximala elementet i $C_{i}$ som tillhör en antikedja med storleken $k$ i $P'$ , och sätt $A:=\{x_ {1},x_{2},\dots ,x_{k}\}$ . Vi hävdar att $A$ är en antikedja. Låt $A_{i}$ vara en antikedja av storleken $k$ som innehåller $x_{i}$ . Fixa godtyckliga distinkta index $i$ och $j$ . Sedan $A_{i}\cap C_{j}\neq \emptyset$ . Låt $y\in A_{i}\cap C_{j}$ . Då är $y\leq x_{j}$ , enligt definitionen av $x_{j}$ . Detta innebär att $x_{i}\not \geq x_{j}$ , eftersom $x_{i}\not \geq y$ . Genom att byta ut rollerna för $i$ och $j$ i detta argument har vi också $x_{j}\not \geq x_{i}$ . Detta verifierar att $A$ är en antikedja.

Vi återgår nu till $P$ . Antag först att $a\geq x_{i}$ för vissa $i\in \{1,2,\dots ,k\}$ . Låt $K$ vara kedjan $\{a\}\cup \{z\in C_{i}:z\leq x_{ i}\}$ . Genom att välja ${\displaystyle x_{i}} har$$P\setminus K}$ displaystyle inte en antikedja med storleken $k$ . Induktion innebär då att $P\setminus K$ kan täckas av $k-1$ disjunkta kedjor eftersom $A\setminus \{x_{i} \}$ är en antikedja med storleken $k-1$ i $P\setminus K$ . Således $P$ täckas av $k$ osammanhängande kedjor efter behov. Därefter, om $a\not \geq x_{i}$ för varje $i\in \{1,2,\dots ,k\ }$ , då är $A\cup \{a\}$ en antikedja av storleken $k+1$ i $P$ (eftersom $a$ är maximal i $P$ ). Nu $P$ täckas av $k+1$ -kedjorna $\{a\},C_{1} ,C_{2},\dots ,C_{k}$ , avslutar beviset.

Bevis via Kőnigs sats

Bevis på Dilworths sats via Kőnigs sats: konstruera en tvådelad graf från en partiell ordning och dela upp i kedjor enligt en matchning

Liksom ett antal andra resultat inom kombinatorik är Dilworths sats likvärdig med Kőnigs sats om tvådelad grafmatchning och flera andra relaterade satser inklusive Halls äktenskapsteorem ( Fulkerson 1956 ).

För att bevisa Dilworths sats för en partiell ordning S med n element, med hjälp av Kőnigs sats, definiera en tvådelad graf G = ( U , V , E ) där U = V = S och där ( u , v ) är en kant i G när u < v i S . Enligt Kőnigs sats finns det en matchande M i G , och en uppsättning av hörn C i G , så att varje kant i grafen innehåller minst en vertex i C och så att M och C har samma kardinalitet m . Låt A vara mängden element i S som inte motsvarar någon vertex i C ; då A minst n - m element (möjligen fler om C innehåller hörn som motsvarar samma element på båda sidor av bipartitionen) och inga två element i A är jämförbara med varandra. Låt P vara en familj av kedjor som bildas genom att inkludera x och y i samma kedja när det finns en kant ( x , y ) i M ; då har P n - m kedjor. Därför har vi konstruerat en antikedja och en uppdelning i kedjor med samma kardinalitet.

För att bevisa Kőnigs sats från Dilworths sats, för en tvådelad graf G = ( U , V , E ), bilda en partiell ordning på hörnen av G där u < v exakt när u är i U , v är i V , och där finns en kant i E från u till v . Enligt Dilworths teorem finns det en antikedja A och en uppdelning i kedjor P som båda har samma storlek. Men de enda icke-triviala kedjorna i den partiella ordningen är par av element som motsvarar kanterna i grafen, så de icke-triviala kedjorna i P bildar en matchning i grafen. Komplementet av A bildar ett vertextäcke i G med samma kardinalitet som denna matchning.

Denna koppling till tvådelad matchning gör att bredden på valfri delordning kan beräknas i polynomtid . Närmare bestämt n -element partiella ordningar av bredd k kännas igen i tiden O ( kn ² ) ( Felsner, Raghavan & Spinrad 2003) .

Utökning till oändligt delbeställda set

Dilworths teorem för oändliga partiellt ordnade mängder säger att en partiellt ordnad mängd har ändlig bredd w om och endast om den kan delas upp i w -kedjor. För anta att en oändlig partiell ordning P har bredd w , vilket betyder att det finns högst ett ändligt antal w element i vilken antikedja som helst. För varje delmängd S av P kan en nedbrytning till w -kedjor (om den finns) beskrivas som en färgning av oförjämförbarhetsgrafen för S (en graf som har elementen i S som hörn, med en kant mellan vartannat ojämförbara element) använder w- färger; varje färgklass i en korrekt färgning av ojämförbarhetsgrafen måste vara en kedja. Genom antagandet att P har bredd w , och genom den finita versionen av Dilworths sats, har varje finit delmängd S av P en w -färgbar ojämförbarhetsgraf. Därför, enligt De Bruijn–Erdős-satsen , har P själv också en w -färgbar ojämförbarhetsgraf, och har därmed den önskade uppdelningen i kedjor ( Harzheim 2005 ).

Men satsen sträcker sig inte så enkelt till delvis ordnade mängder där bredden, och inte bara mängdens kardinalitet, är oändlig. I detta fall kan storleken på den största antikedjan och det minsta antalet kedjor som behövs för att täcka den partiella ordningen skilja sig mycket från varandra. Speciellt för varje oändligt kardinaltal κ ​​finns det en oändlig partiellt ordnad uppsättning av bredd ℵ ₀ vars uppdelning i de minsta kedjorna har κ-kedjor ( Harzheim 2005 ).

Perles (1963) diskuterar analoger till Dilworths teorem i den oändliga miljön.

Dual av Dilworths teorem (Mirskys teorem)

Huvudartikel: Mirskys teorem

En dual av Dilworths teorem säger att storleken på den största kedjan i en partiell ordning (om ändlig) är lika med det minsta antalet antikedjor som ordningen kan delas in i (Mirsky 1971 ) . Beviset för detta är mycket enklare än beviset för själva Dilworths sats: för alla element x , betrakta kedjorna som har x som sitt största element, och låt N ( x ) beteckna storleken på den största av dessa x -maximala kedjor. Då är varje uppsättning N ⁻¹ ( i ), som består av element som har lika värden på N , en antikedja, och dessa antikedjor delar upp den partiella ordningen i ett antal antikedjor 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 en vertex per element i ordningen och en kant som förbinder två jämförbara element. Således motsvarar en klick i en jämförbarhetsgraf en kedja, och en oberoende uppsättning i en jämförbarhetsgraf motsvarar en antikedja. Varje inducerad subgraf av en jämförbarhetsgraf är i sig en jämförbarhetsgraf, bildad från begränsningen av den partiella ordningen till en delmängd av dess element.

En oriktad graf är perfekt om, i varje inducerad subgraf, det kromatiska talet är lika med storleken på den största klicken. Varje jämförbarhetsgraf är perfekt: detta är i huvudsak bara Mirskys teorem, omräknat i grafteoretiska termer ( Berge & Chvátal 1984) . Enligt den perfekta grafsatsen av Lovász (1972) är komplementet till varje perfekt graf också perfekt. Därför är komplementet till alla jämförbarhetsdiagram perfekt; detta är i huvudsak bara Dilworths sats själv, omformulerad i grafteoretiska termer ( Berge & Chvátal 1984) . Således kan komplementeringsegenskapen för perfekta grafer ge ett alternativt bevis för Dilworths teorem.

Bredd på särskilda delbeställningar

Det booleska gittret B _n är potensmängden av en n -elementmängd X — väsentligen {1, 2, …, n }—ordnad efter inkludering eller, notationsmässigt, (2 ^{[ n ]} , ⊆). Sperners teorem säger att en maximal antikedja av B _n har storlek som mest

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

Med andra ord, en största familj av ojämförliga delmängder av X erhålls genom att välja delmängder av X som har medianstorlek. Lubell –Yamamoto–Meshalkin-ojämlikheten gäller också antikedjor i en kraftuppsättning och kan användas för att bevisa Sperners sats.

Om vi ​​ordnar heltalen i intervallet [1, 2 n ] efter delbarhet bildar delintervallet [ n + 1, 2 n ] en antikedja med kardinalitet n . En uppdelning av denna delordning i n kedjor är lätt att uppnå: för varje udda heltal m i [1,2 n ], bilda en kedja av talen i formen m 2 ⁱ . Därför, enligt Dilworths teorem, ä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 ordningsföljder dimension två ( Steele 1995 ).

Den "konvexa dimensionen" av en antimatroid definieras som det minsta antalet kedjor som behövs för att definiera antimatroiden, och Dilworths teorem kan användas för att visa att den är lika med bredden på en tillhörande partiell ordning; denna koppling leder till en polynomisk tidsalgoritm för konvex dimension ( Edelman & Saks 1988) .

•   Berge, Claude ; Chvátal, Václav (1984), Ämnen om perfekta grafer , Annals of Discrete Mathematics, vol. 21, Elsevier, sid. 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 , JSTOR 1969503 .
•   Edelman, Paul H.; Saks, Michael E. (1988), "Kombinatorisk representation och konvex dimension av konvexa geometrier", Order , 5 (1): 23–32, doi : 10.1007/BF00143895 , S2CID 119826035 .
•    Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Igenkänningsalgoritmer för beställningar av liten bredd och grafer av små Dilworth-tal" , Order , 20 ( 4): 351–364 (2004), doi : 10.1023 /B:ORDE.0000034609.fb 4609.fb 4609.fb 4609.fb 2079151 , S2CID 1363140 .
•   Fulkerson, DR (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 , JSTOR 2033375 .
•    Galvin, Fred (1994), "A proof of Dilworth's chain decomposition theorem", The American Mathematical Monthly , 101 (4): 352–353, doi : 10.2307/2975628 , JSTOR 2975628 , MR 1270960 .
• Greene, Curtis ; Kleitman, Daniel J. (1976), "The structure of Sperner $k$ -families", Journal of Combinatorial Theory, Series A , 20 (1): 41–68, doi : 10.1016/0097-3165(76) )90077-7 .
•    Harzheim, Egbert (2005), Ordered sets , Advances in Mathematics (Springer), vol. 7, New York: Springer, Theorem 5.6, sid. 60, ISBN 0-387-24219-8 , MR 2127991 .
• Lovász, László (1972), "Normala hypergrafer och den perfekta grafförmodan", 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 , JSTOR 2316481 .
•    Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, sid. 42, doi : 10.1007/978-3-642-27875-4 , hdl : 10338.dmlcz/143192 , ISBN 978-3-642-27874-7 , MR 2920058 .
•    Perles, Micha A. (1963), "On Dilworth's theorem in the infinite case", Israel Journal of Mathematics , 1 (2): 108–109, doi : 10.1007/BF02759806 , MR 0168497 , S2CID 0650 .
• Steele, J. Michael (1995), "Variationer på det monotona efterföljdstemat av Erdős och Szekeres", i Aldous, David ; Diaconis, Persi ; Spencer, Joel ; et al. (red.), Discrete Probability and Algorithms (PDF) , IMA Volumes in Mathematics and its Applications, vol. 72, Springer-Verlag, s. 111–131 .

externa länkar

• Ekvivalens av sju stora satser i kombinatorik
• "Dual of Dilworth's Theorem" , PlanetMath , arkiverad från originalet 2007-07-14
• Babai, László (2005), Lecture Notes in Combinatorics and Probability, Lecture 10: Perfect Graphs (PDF) , arkiverad från originalet (PDF) 2011-07-20
• Felsner, S.; Raghavan, V. & Spinrad, J. (1999), Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
• Weisstein, Eric W. "Dilworths Lemma" . MathWorld .