Dilworths sætning

Dilworths sætning er et kombinatorisk udsagn, der karakteriserer en ekstremal egenskab for posetter : en endelig poset kan opdeles i parvise usammenhængende kæder , hvor er antallet af elementer i den største antikæde i sættet [1] (også kaldet bredden af poset) . $EN$ $n$ $n$ $EN$

En version af sætningen for uendelige posetter: En poset har begrænset bredde , hvis og kun hvis den kan nedbrydes i kæder, men ikke mindre. $w$ $w$

Det blev bevist af den amerikanske matematiker Robert P. Dilworth ( 1914-1993), hvis hovedområde for forskning var gitterteori .

Bevis ved induktion

Beviset ved induktion på størrelsen af et poset er baseret på Galvins bevis [2] . $M$

Lad være et endeligt delvist ordnet sæt. Udsagnet er trivielt, hvis det er tomt. Så antag, at det har mindst ét element, og lad være det maksimale element af . $M$ $M$ $M$ $-en$ $M$

Ved induktionshypotesen kan en poset for nogle heltal være dækket af usammenhængende kæder og har mindst én antikæde af størrelse . Det er klart, at for . For , lad være det maksimale element i , som hører til antikæden af størrelse i og til sættet . Vi hævder, at det er en antikæde. Lade være en antikæde af størrelse indeholdende . Lad os rette vilkårlige adskilte indekser og . Så . Lad . Så per definition . Det følger heraf , at siden . Hvis vi bytter rollerne og , får vi . Dette beviser, at det er en antikæde. $k$ $M':=M\setminus \{a\}$ $k$ $C_{1},\dots ,C_{k}$ $A_0$ $k$ $A_{0}\cap C_{i}\neq \emptyset$ $i=1,2,\prikker ,k$ $i=1,2,\prikker ,k$ $x_{i}$ $C_{i}$ $k$ $M'$ $A:=\{x_{1},x_{2},\dots ,x_{k}\}$ $EN$ $A_{i}$ $k$ $x_{i}$ $jeg$ $j$ $A_{i}\cap C_{j}\neq \emptyset$ $y\in A_{i}\cap C_{j}$ $y\leq x_{j}$ $x_{j}$ $x_{i}\ikke \geq x_{j}$ $x_{i}\ikke \geq y$ $jeg$ $j$ $x_{j}\ikke \geq x_{i}$ $EN$

Lad os gå tilbage til . Antag først, at for nogle . Lad være en kæde . Så, på grund af valget , indeholder ikke en antikæde af størrelse . Det følger af induktionshypotesen, at det er muligt at dække med usammenhængende baner, da er en antikæde af størrelse i . Det er således muligt at dække med ikke-krydsende kæder efter behov. $M$ $a\geq x_{i}$ $i\in \{1,2,\prikker ,k\}$ $K$ $\{a\}\kop \{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, hvis for hver , så er en antikæde af størrelse i (da er maksimum i ). Således kan være dækket af kæder , som fuldender beviset. $a\ikke \geq x_{i}$ $i\in \{1,2,\prikker ,k\}$ $A\kop \{a\}$ $k+1$ $M$ $-en$ $M$ $M$ $k+1$ $\{a\},C_{1},C_{2},\dots ,C_{k}$

Bevis via Königs sætning

Som andre resultater af kombinatorik svarer Dilworths sætning til Königs sætning om matchninger på todelte grafer og nogle andre sætninger, herunder Halls bryllupssætning [3] .

For at bevise Dilworths sætning for en sætning S med n elementer, ved hjælp af Königs sætning, definerer vi en todelt graf G = ( U , V , E ) hvor U = V = S og ( u , v ) er en kant i G hvis u < v til S. _ Ved Königs sætning er der en matchende M i G , og et sæt toppunkter C i G , således at hver kant fra grafen indeholder mindst et toppunkt fra C , og begge mængder, M og C , har det samme antal elementer m . Lad A være mængden af elementer af S , der ikke svarer til noget toppunkt i C . Så har A mindst n - m elementer (evt. flere, hvis C indeholder toppunkter svarende til det samme element på begge sider af den todelte graf). Lad P være familien af kæder dannet ved at inkludere x og y i en kæde, når der er en kant ( x , y ) i M. Så har P n - m kæder. Vi har således konstrueret en antikæde og en nedbrydning til kæder med det samme antal elementer i sættet.

For at bevise Königs sætning fra Dilworths sætning for en todelt graf G = ( U , V , E ) danner vi en delrækkefølge på hjørnerne af G ved at sætte u < v nøjagtigt når u er indeholdt i U , v er indeholdt i V og der er en kant fra E fra u i v . Ved Dilworths sætning er der en antikæde A og en kædenedbrydning P , begge sæt af samme størrelse. Men kun par af elementer, der svarer til grafens kanter, kan være ikke-trivielle kæder i delvis rækkefølge, så ikke-trivielle kæder fra P danner en matchning i grafen. Komplement A danner et toppunktsdæksel G med det samme antal elementer som i matchningen.

Denne forbindelse med bipartite matchninger gør det muligt at beregne bredden af ethvert ordnet sæt i polynomiel tid .

Generalisering til ubegrænsede delvist ordnede sæt

Dilworths sætning for ubundne delvist ordnede mængder siger, at et sådant sæt har begrænset bredde w, hvis og kun hvis det kan dekomponeres i w - kæder. Antag, at en uendelig poset P har bredden w , hvilket betyder, at enhver antikæde højst indeholder et endeligt antal w af elementer. For enhver delmængde S af P kan nedbrydningen i w -kæder (hvis den findes) beskrives som en farvning af uforlignelsesgrafen S (en graf, der har elementer af S som toppunkter og kanter for uforlignelige toppunkter) ved brug af w- farver. Enhver farveklasse i en uforlignelig graf skal være en kæde. Hvis vi antager, at P har bredden w , ved den endelige kasusversion af Dilworths sætning, har enhver finit delmængde S af P en w -farvning af uforlignelsesgrafen. Ved de Bruijn-Erdős-sætningen har P således også selv en w -farvning af uforlignelsesgrafen, og dette er den ønskede opdeling i kæder [4] .

Sætningen generaliserer dog ikke så let til tilfældet med posetter, hvor bredden ikke er afgrænset. I dette tilfælde kan størrelsen af den maksimale antistreng og det mindste antal strenge, der kræves til dækning, variere betydeligt. Især for ethvert uendeligt kardinaltal κ eksisterer der et uendeligt delvist ordnet sæt med bredden ℵ 0 , hvis opdeling i kæder har mindst κ-kæder [4] .

I 1963 [5] blev der opnået et udsagn svarende til Dilworths teorem for det ubegrænsede tilfælde.

Mirskys sætning

Sætningen dual til Dilworths sætning, Mirskys sætning , hævder, at størrelsen af den største kæde i en partiel orden (det sidste tilfælde) er lig med det mindste antal antikæder, hvori den partielle orden kan dekomponeres [6 ] . Beviset for denne sætning er meget enklere end Dilworths sætning. For ethvert element x skal du tage kæder, der har x som deres maksimale element, og lade N ( x ) være størrelsen af den største af disse x -maksimum- kæder. Så er hvert sæt N −1 ( i ) bestående af elementer, der har samme værdier af N , en antikæde, og størrelsen af denne opdeling af et delvist ordnet sæt i antikæder er lig med størrelsen af den største kæde.

Perfektion af sammenlignelighedsgrafer

En sammenlignelighedsgraf er en urettet graf, der er dannet ud fra en delvis rækkefølge ved at skabe hjørner for hvert element i rækkefølgen og kanter for to sammenlignelige elementer. En klike i sammenlignelighedsgrafen svarer således til en kæde, og et uafhængigt sæt svarer til en antikæde. Enhver genereret undergraf af en sammenlignelighedsgraf er i sig selv en sammenlignelighedsgraf dannet ud fra en delvis rækkefølge ved at indsnævre til en undergruppe af elementer.

En urettet graf er perfekt , hvis det kromatiske tal i hver genereret undergraf er lig med størrelsen af den største klike. Enhver sammenlignelighedsgraf er perfekt - dette er blot Mirskys teorem, genfortalt i form af grafteori [7] . Ved Lovas ' perfekte grafsætning [8] er komplementet til enhver perfekt graf også en perfekt graf. Således er komplementet af enhver sammenlignelighedsgraf perfekt. Dette er i det væsentlige det samme Dilworths teorem formuleret i form af grafteori [7] . Komplementaritetsegenskaben ved perfekte grafer kan således give et alternativt bevis på Dilworths sætning.

Bredde af særlige delordrer

Det boolske gitter B n er graden af et sæt X af n elementer - f.eks. {1, 2, …, n } - ordnet efter inklusion eller formelt (2 [ n ] , ⊆). Sperners sætning siger, at den maksimale antikæde i B n har en størrelse, der ikke overstiger

{\mbox{width}}(B_{n})={n \vælg \lgulv {n/2}\rgulv }.

Med andre ord opnås den største familie af uforlignelige delmængder af mængder X ved at vælge delmængder af X , der har et middelværdi. Lubell-Yamamoto-Meshalkin-uligheden er også relateret til antikæder i potenser af et sæt og kan bruges til at bevise Sperners sætning.

Hvis du bestiller heltal i intervallet [1, 2 n ] efter delelighed , danner underintervallet [ n + 1, 2 n ] en antikæde af størrelse n . Dekomponeringen af denne delrækkefølge i n kæder er let at opnå: for hver ulige m i [1,2 n ] danner vi en talkæde af formen m 2 i . Ved Dilworths sætning er bredden af denne partielle orden n .

Erdős-Szekeres-sætningen om monotone delsekvenser kan tolkes som en anvendelse af Dilworth-sætningen på partielle dimensionsordener to [9] .

Den "konvekse dimension" af en antimatroide er defineret som det mindste antal kæder, der er nødvendige for at definere en antimatroide, og Dilworths teorem kan bruges til at vise, at den er lig med bredden af den tilhørende partielle orden. Dette forhold fører til en tids-lineær algoritme til at finde en konveks dimension [10] .

Noter

↑ Marshall Hall Jr. Kombinatorisk teori. - "MIR", 1970. - S. 90-94. Arkiveret 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 og algoritmer. - Heidelberg: Springer, 2012. - T. 28. - S. 42. - (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7 . - doi : 10.1007/978-3-642-27875-4 .
Egbert Harzheim. bestilte sæt. - New York: Springer, 2005. - V. 7. - S. Sætning 5.6, s.60. - (Fremskridt i matematik (Springer)). - ISBN 0-387-24219-8 .
Claude Berge, Václav Chvatal. Emner om perfekte grafer. - Elsevier, 1984. - T. 21 . - C. viii . — ISBN 9780444865878 .
Robert P. Dilworth. En dekomponeringssætning for delvist ordnede mængder // Annals of Mathematics . - 1950. - T. 51 , no. 1 . - S. 161-166 . - doi : 10.2307/1969503 .
Paul H. Edelman, Michael E. Saks. Kombinatorisk repræsentation og konveks dimension af konvekse geometrier // Orden . - 1988. - V. 5 , no. 1 . - S. 23-32 . - doi : 10.1007/BF00143895 .
D.R. Fulkerson. Bemærkning om Dilworths dekomponeringssætning for delvist ordnede sæt // Proceedings of the American Mathematical Society . - 1956. - Bd. 7 , iss. 4 . - S. 701-702 .
Fred Galvin. Et bevis på Dilworths kædenedbrydningssætning // The American Mathematical Monthly . - 1994. - T. 101 , no. 4 . - S. 352-353 . - doi : 10.2307/2975628 .
Laszlo Lovasz. Normale hypergrafer og den perfekte grafformodning // Diskret matematik . - 1972. - T. 2 . - S. 253-267 . - doi : 10.1016/0012-365X(72)90006-4 .
Leon Mirsky. En dual af Dilworths dekomponeringssætning // American Mathematical Monthly . - 1971. - T. 78 , no. 8 . - S. 876-877 . - doi : 10.2307/2316481 . .
Micha A. Perles. Om Dilworths sætning i det uendelige tilfælde // Israel Journal of Mathematics. - 1963. - T. 1 . - S. 108-109 . - doi : 10.1007/BF02759806 .
J. Michael Steele. Diskrete sandsynlighed og algoritmer / David Aldous, Persi Diaconis, Joel Spencer, J. Michael Steele. - Springer-Verlag, 1995. - T. 72. - S. 111-131. - (IMA Volumes in Mathematics and its Applications).
A. V. Spivak, Chains and antichains , Moskva Center for Fortsat Matematisk Uddannelse , materialer fra den besøgende matematiske skole, 7-11.04.2004.]
Ækvivalens af syv store sætninger i kombinatorik
Dual of Dilworth's Theorem (ikke tilgængeligt link) . PlanetMath . Hentet 12. juni 2011. Arkiveret fra originalen 14. juli 2007. (ubestemt)
Babai, Laszlo. Lecture notes in Combinatorics and Probability, Forelæsning 10: Perfect Graphs (2005). Hentet 12. juni 2011. Arkiveret fra originalen 14. maj 2012. (ubestemt)
Felsner, S., Raghavan, V., og Spinrad, J. Genkendelsesalgoritmer for rækkefølger af lille bredde og grafer af små Dilworth-tal (1999). Hentet 12. juni 2011. Arkiveret fra originalen 14. maj 2012. (ubestemt)
Weisstein, Eric W. Dilworth's Lemma (engelsk) på Wolfram MathWorld -webstedet .