Informatyka MIMUW

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:

• $x\leq x$ (zwrotność),

• $x \leq y$, $y \leq x$ implikuje $x = y$ (antysymetria),

• $x \leq y$, $y \leq z$ implikuje $x \leq z$ (przechodniość).

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:

• Umieszczamy punkty obrazujące elementy zbioru $X$ na płaszczyźnie,oznaczając je małymi kółkami.

Dla elementów $x,y\in X$, jeśli $y < x$, to punkt przypisany elementowi $x$ jest powyżej punktu przypisanemu elementowi $y$.

• Łączymy odcinkiem punkt $x\in X$ z punktem $y\in X$, jeśli $x$ jest następnikiem $y$, czyli $y < x$ oraz nie istnieje $z\in X$, taki że $y < z < x$.

Ł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:

• $x\leq y$ oraz $x\leq y$ (liniowość).

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:

• $x\not\leq y$ oraz $x\not\leq y$ (niezależność).

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:

• ${\sf width}\!( P- C )=w-1$

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$.

• ${\sf width}\!( P- C )=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:

$(*)$ w zbiorze \( p\!\uparrow=\lbrace x\in P

p\leq x \rbrace \)

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.