Zbiór częściowo uporządkowany (poset) to para \( \mathbf{P}=( X,\leq ) \), gdzie \( X \) jest zbiorem, zaś \( \leq \) jest dwuargumentową relacją określoną na \( X \), która dla dowolnie wybranych \( x,y,z\in X \) spełnia:
Uwaga
Częściowy porządek wygodnie przedstawiać jest przy użyciu tzw. diagramu Hassego, który przedstawia się na płaszczyźnie \( \mathbb{R}^2 \) w następujący sposób:
Dla elementów \( x,y\in X \), jeśli \( y < x \), to punkt przypisany elementowi \( x \) jest powyżej punktu przypisanemu elementowi \( y \).
Łańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( C \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Antyłańcuch w zbiorze częściowo uporządkowanym \( \mathbf{P}=( X,\leq ) \) to taki podzbiór \( A \) zbioru \( X \), że dla dowolnych \( x,y\in X \) zachodzi:
Szerokość posetu \( \mathbf{P}=( X,\leq ) \) to maksymalny możliwy rozmiar antyłańcucha w \( \mathbf{P} \). Szerokość oznaczana będzie za pomocą \( {\sf width}\!( \mathbf{P} ) \).
W ogólności szerokość \( {\sf width}\!( Y ) \) można zdefiniować dla dowolnego podzbioru \( Y\subseteq X \), jako największy możliwy rozmiar antyłańcucha zawartego w \( Y \).
Pokrycie łańcuchowe posetu \( \mathbf{P}=( X,\leq ) \) to taka rodzina łańcuchów \( C_1,\ldots C_k \), że
Twierdzenie 2.1 [R. P. Dilworth 1950]
Minimalna liczba łańcuchów pokrywających poset \( \mathbf{P} \) jest równa szerokości posetu \( \mathbf{P} \).
Dowód
Oczywiście liczba łańcuchów pokrywających poset nie może być mniejsza niż jego szerokość, bo każdy punkt w antyłańcuchu realizującym tę szerokość musi być pokryty innym łańcuchem.
Dowód implikacji odwrotnej przeprowadzimy indukcyjnie ze względu na liczność \( n \) posetu \( \mathbf{P}=( P,\leq ) \). Niech \( w={\sf width}\!( \mathbf{P} ) \). Rozważmy maksymalny, w sensie inkluzji, łańcuch \( C \) zawarty w \( \mathbf{P} \). Po usunięciu łańcucha \( C \) szerokość posetu może zmniejszyć się co najwyżej o jeden. Dowód podzielimy więc na dwa przypadki:
Na mocy założenia indukcyjnego poset \( P- C \) daje się pokryć \( w-1 \) łańcuchami, które wobec tego wraz z \( C \) tworzą szukane pokrycie całego posetu \( \mathbf{P} \) za pomocą \( w \).
Niech \( A \) bedzie antyłańcuchem realizującym szerokość zbioru \( P- C \), tzn. \( \vert A \vert=w \). Połóżmy:
Jeśli \( U=P \), to łańcuch \( C \) całkowicie zawiera się w \( U \). Z definicji zbioru \( U \) wynika, że istnieje element \( a_0\in A \), który jest mniejszy od najmniejszego elementu łańcucha \( C \), a tym samym od wszystkich elementów w \( C \). Skoro \( A \subseteq P- C \), to \( a_0\not\in C \) i w konsekwencji \( \lbrace a_0 \rbrace\cup C \) jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha \( C \). To pokazuje, że \( \vert U \vert < \vert P \vert \). Podobnie możemy uzasadnić, że również \( \vert D \vert < \vert P \vert \). Do obu zbiorów \( U,D \) możemy więc zastosować założenie indukcyjne, dostając ich pokrycia łańcuchowe
\( U=C_1\cup\ldots\cup C_w,\quad D=C_1'\cup\ldots\cup C_w'. \)
Ponieważ \( A \subseteq D \cap U \), to każdy element z \( A \) należy do jakiegoś łańcucha \( C_i \) i do jakiegoś łańcucha \( C_j' \). Z drugiej strony fakt, że \( A \) jest \( w \)-elementowym antyłańcuchem gwarantuje, że w każdym łańcuchu postaci \( C_i \) lub \( C_j' \) jest jakiś element z \( A \). Pozwala to na takie przenumerowanie łańcuchów \( C_i \) i \( C_j' \), by \( C_i\cap C_j'\neq \emptyset \), tzn. że dla \( a\in A \) mamy \( a \in C_i \) wtedy i tylko wtedy, gdy \( a\in C_i' \). To z kolei oznacza, że każda suma \( C_i\cup C_i' \) jest łańcuchem. Oczywiście te nowe łańcuchy \( C_i\cup C_i' \) pokrywają zbiór \( D\cup U \). Zauważmy jednak, że \( D\cup U=P \), bo inaczej istniałby element \( p\in P \) nieporównywalny z żadnym elementem antyłańcucha \( A \), czyli \( A\cup \lbrace p \rbrace \) byłby antyłańcuchem istotnie większym niż maksymalny antyłańcuch \( A \). W konsekwencji otrzymujemy pokrycie łańcuchowe
\( P=(C_1\cup C_1')\cup\ldots\cup(C_w\cup C_w') \)
całego zbioru \( P \).
Pokrycie antyłańcuchowe posetu \( \mathbf{P}=( X,\leq ) \) to taka rodzina antyłańcuchów \( A_1,\ldots A_k \), że
\( A_1\cup\ldots\cup A_k=X. \)
Twierdzenie 2.2 [Dualne Twierdzenie Dilworth'a]]
Minimalna liczba antyłańcuchów pokrywających poset \( \mathbf{P}=( P,\leq ) \) jest równa maksymalnej liczności łańcucha zawartego w \( \mathbf{P} \).
Pokrycie antyłańcuchowe posetu \( \mathbf{P}_0 \)
Dowód
Moc najdłuższego łańcucha oznaczmy przez \( h \). Niech \( A_i \) będzie zbiorem elementów \( p\in P \) spełniających:
najliczniejszy łańcuch jest mocy \( i \).
Pokażemy, że każde \( A_i \) jest antyłańcuchem. Istotnie, gdyby dwa różne elementy \( p_1,p_2\in A_i \) były porównywalne, to możemy bez straty ogólności założyć, że \( p_1 < p_2 \). Ponieważ \( p_2 \in A_i \), to w zbiorze \( p_2\!\uparrow \) jest łańcuch o liczności \( i \).
Łańcuch ten jednak można by przedłużyć (od dołu) do liczniejszego łańcucha \( \lbrace p_1 \rbrace\cup C_2 \). To oczywiście przeczy temu, że \( p_1\in A_i \). Zatem istotnie każde \( A_i \) jest antyłańcuchem. Intuicyjnie antyłańcuchy \( A_i \) to kolejne piętra posetu \( \mathbf{P} \). Oczywiście każdy punkt \( p \in P \) musi być w którymś ze zbiorów \( A_1,\ldots,A_h \), bo \( p\!\uparrow \) nie może zawierać łańcuchów liczniejszych niż \( h \). Dostaliśmy więc następujące pokrycie antyłańcuchami:
Oczywiście pokrycie to jest najmniej liczne, bo w każdym pokryciu każdy spośród \( h \) punktów najdłuższego łańcucha musi leżeć w innym antyłańcuchu.
Wniosek 2.3
Każdy zbiór częściowo uporządkowany o \( rs+1 \) elementach zawiera łańcuch o liczności \( r+1 \) lub antyłańcuch o liczności \( s+1 \).
Dowód
Niech \( \mathbf{P}=( P,\leq ) \) będzie posetem, w którym każdy łańcuch jest liczności co najwyżej \( r \), a każdy antyłańcuch jest liczności co najwyżej \( s \). Dualne Twierdzenie Dilworth'a 2.2 dostarcza pokrycie antyłańcuchami
\( P=A_1\cup\ldots\cup A_{r'}, \)
gdzie \( r'\leq r \) jest mocą łańcucha o maksymalnej liczności. Ponieważ \( \vert A_i \vert\leq s \), to
\( \vert P \vert=\vert A_1 \vert+\ldots+\vert A_{r'} \vert\leq r's\leq rs. \)
Sprzeczność ta pokazuje, że jeśli \( \mathbf{P} \) ma co najmniej \( rs+1 \) elementów, to musi zawierać łańcuch o liczności \( r+1 \) lub antyłańcuch o liczności \( s+1 \).
Uwaga
Dowód wniosku 2.3 można równie dobrze przeprowadzić opierając się na Twierdzeniu Dilworth'a 2.1, co pozostawiamy jako ćwiczenie 3.
Jednym z ciekawszych wniosków z Twierdzenia Dilworth'a jest fakt, że każdy ciąg \( r^2+1 \) liczb rzeczywistych zawiera podciąg monotoniczny o \( r+1 \) elementach. Pierwszy dowód tego twierdzenia przedstawili P. Erd{o}s oraz G. Szekres w 1939 roku. Poniżej przedstawione jest uogólnienie tego twierdzenia, którego uzasadnienie będzie korzystało z wniosku 2.3.
Twierdzenie 2.4
Każdy ciąg \( n\geq rs+1 \) liczb rzeczywistych zawiera podciąg niemalejący o długości \( r+1 \) lub podciąg malejący o długości \( s+1 \).
Dowód
Niech \( A=( a_1,\ldots,a_n ) \) będzie ciągiem liczb rzeczywistych. Na parach postaci \( ( i,a_i ) \), wprowadzamy relację częściowego porządku kładąc
\( ( i,a_i )\leq( j,a_j ) \) wtedy i tylko wtedy, gdy \( i\leq j \) oraz \( a_i\leq a_j \).
Łańcuchy w tym porządku, to nic innego jak podciągi niemalejące ciągu \( A \), a antyłańcuchy to podciągi malejące ciągu \( A \). Po tym utożsamieniu wystarczy powołać się na Wniosek 2.3.