Twierdzenie Dilwortha

Twierdzenie Dilwortha – twierdzenie kombinatoryczne o charakterze minimaksowym dotyczące struktury zbiorów częściowo uporządkowanych. Zgodnie z twierdzeniem Dilwortha w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczność antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają ten zbiór.

Twierdzenie to zostało sformułowane przez amerykańskiego matematyka Roberta Dilwortha, który opublikował jego dowód w 1950 roku.

Twierdzenie

Szablon:Zobacz też Niech $\preccurlyeq$ będzie relacją częściowego porządku na zbiorze $X$. Łańcuchem nazywa się zbiór $L\subseteq X,$ w którym każde dwa elementy są porównywalne, czyli zbiór $L$ jest uporządkowany liniowo przez relację $\preccurlyeq .$ Z kolei podzbiór $A\subseteq X,$ w którym każde dwa elementy są nieporównywalne, nazywa się antyłańcuchem. Minimalna liczba łańcuchów, które pokrywają zbiór $X,$ to najmniejsza taka liczba całkowita $n,$ że istnieją łańcuchy $L_1,L_2,\dots ,L_n\subseteq X,$ dla których zachodzi $X=L_1\cup L_2\cup \dots \cup L_n$.

Twierdzenie Dilwortha orzeka, że jeśli zbiór $X$ jest skończony, to maksymalna liczność (moc) antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają zbiór $X$. Twierdzenie to jest prawdziwe również, gdy zbiór $X$ jest nieskończony, ale maksymalna moc antyłańcucha w tym zbiorze jest skończona.

Dowód

Przedstawiony tu dowód indukcyjny podał Helge Tverberg w 1967 roku.

Stosujemy indukcję względem mocy zbioru $X.$ Przypadek $|X|\le 1$ jest oczywisty. Załóżmy teraz, że twierdzenie jest prawdziwe dla wszystkich zbiorów liczących mniej niż $n$ elementów. Przyjmijmy $|X|=n$ i niech $m$ będzie maksymalną licznością antyłańcucha w tym zbiorze, a $L$ dowolnym maksymalnym (czyli takim, którego nie można powiększyć) łańcuchem. Oczywiście zbioru $X$ nie możemy pokryć mniej niż $m$ łańcuchami, ponieważ każdy łańcuch może zawierać co najwyżej jeden element antyłańcucha.

Jeśli każdy antyłańcuch w zbiorze $X\setminus L$ ma co najwyżej $m-1$ elementów, to na mocy założenia indukcyjnego $X$ jest sumą łańcucha $L$ oraz $m-1$ łańcuchów, które pokrywają $X\setminus L.$

Załóżmy zatem, że w $X\setminus L$ istnieje antyłańcuch $m$-elementowy $A=\{a_1,a_2,\dots ,a_m\}.$ Ponieważ każdy antyłańcuch w $X\setminus L$ jest też antyłańcuchem w $X,$ antyłańcuch $A$ jest maksymalnej liczności. Utwórzmy zbiory Szablon:Wzór Szablon:WzórNiech $c$ będzie najmniejszym elementem łańcucha $L.$ Oczywiście $c\in ̸G$ – w przeciwnym wypadku łańcuch $L$ można by powiększyć. Analogicznie $D$ nie zawiera największego elementu $L.$ Stąd $|G|<|X|$ oraz $|D|<|X|$ i na mocy założenia indukcyjnego istnieją rozkłady na łańcuchy Szablon:Wzór Szablon:Wzór

Bez straty ogólności niech $a_i\in G_i$ oraz $a_i\in D_i.$ Jeśli $a_i$ nie jest najmniejszym elementem $G_i,$ to dla pewnych $x\in G_i,$ $a\in A$ zachodzi $a\preccurlyeq x\preccurlyeq a_i,$ co jest sprzeczne z definicją antyłańcucha. Analogicznie dowodzi się, że $a_i$ jest największym elementem $D_i.$ Zauważmy, że $X=G\cup D,$ ponieważ w przeciwnym wypadku antyłańcuch $A$ można by powiększyć o pewien element $x\in X\setminus (G\cup D).$ Stąd Szablon:Wzórjest rozkładem zbioru $X$ na $m$ łańcuchów. Wobec dowolności zbioru $X$ teza zachodzi dla wszystkich zbiorów o mocy $n,$ co kończy dowód indukcyjny.

Twierdzenie dualne

Twierdzenie Dilwortha pozostaje prawdziwe, gdy w jego sformułowaniu zamienimy miejscami sformułowania „łańcuch” i „antyłańcuch”. Taką postać twierdzenia nazywa się dualnym twierdzeniem Dilwortha. Dowód tego twierdzenia przedstawił Leon Mirsky w 1971 roku.

Dualne twierdzenie Dilwortha orzeka, że w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczność łańcucha jest równa minimalnej liczbie antyłańcuchów, które pokrywają ten zbiór.

Podobnie jak twierdzenie Dilwortha, twierdzenie dualne jest prawdziwe również dla zbiorów nieskończonych pod warunkiem, że maksymalna liczność łańcucha jest ograniczona.

Zastosowania

Twierdzenie Erdősa–Szekeresa

Każdy ciąg liczb rzeczywistych o $nm+1$ wyrazach zawiera podciąg niemalejący długości $n+1$ lub podciąg nierosnący długości $m+1.$

Niech $(a_1,a_2,\dots ,a_{nm+1})$ będzie dowolnym takim ciągiem. Wprowadźmy w zbiorze $A=\{(k,a_k):1\le k\le nm+1\}$ relację Szablon:Wzór Podciąg $(a_{k_1},a_{k_2},\dots ,a_{k_l})$ jest niemalejący wtedy i tylko wtedy, gdy odpowiadający mu zbiór par tworzy łańcuch w $A$ i nierosnący, gdy zbiór ten tworzy antyłańcuch. Jeśli najliczniejszy antyłańcuch w $A$ ma co najmniej $m+1$ elementów, to natychmiast otrzymujemy tezę. W przeciwnym wypadku zbiór $A$ jest sumą $m$ łańcuchów. Wówczas na mocy zasady szufladkowej Dirichleta istnieje łańcuch o mocy nie mniejszej niż $\frac{nm+1}{m}=n+\frac{1}{m},$ czyli co najmniej $n+1.$ To kończy dowód.

Rozkład zbioru potęgowego na sumę łańcuchów

Rozważmy $(𝒫(A),\subseteq )$ – rodzinę wszystkich podzbiorów zbioru $A$ uporządkowaną przez relację zawierania. Twierdzenie Spernera mówi, że najliczniejszy antyłańcuch w tym zbiorze ma $(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$ elementów. Z twierdzenia Dilwortha wynika, że $𝒫(A)$ można przedstawić jako sumę $(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })$ łańcuchów. Ponadto jest to najmniejsza liczba o tej własności.

Zobacz też

• twierdzenie Spernera
• częściowy porządek
• krata