Matematyka dyskretna 2/Wykład 2: Porządki Częściowe i twierdzenie Dilworth'a

From Studia Informatyczne



Diagram Hassego przykładowego porządku \mathbf{P}_0


Łańcuch (a) oraz antyłańcuch (b) w posecie \mathbf{P}_0


Antyłańcuch realizujący szerokość (a) oraz pokrycie łańcuchowe (b) posetu \mathbf{P}_0

Zbiór częściowo uporządkowany (poset) to para \mathbf{P}=\left( X,\leq \right), 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}=\left( X,\leq \right) 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}=\left( X,\leq \right) 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}=\left( X,\leq \right) to maksymalny możliwy rozmiar antyłańcucha w \mathbf{P}. Szerokość oznaczana będzie za pomocą {\sf width}\!\left( \mathbf{P} \right).
W ogólności szerokość {\sf width}\!\left( Y \right) 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}=\left( X,\leq \right) to taka rodzina łańcuchów C_1,\ldots C_k, że


C_1\cup\ldots\cup C_k=X.


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}=\left( P,\leq \right). Niech w={\sf width}\!\left( \mathbf{P} \right). 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}\!\left( P- C \right)=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}\!\left( P- C \right)=w

Niech A bedzie antyłańcuchem realizującym szerokość zbioru P- C, tzn. \left\vert A \right\vert=w. Połóżmy:


\aligned U=\left\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie ,że }p\geq a  \right\rbrace,\\ D=\left\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie, że }p\leq a  \right\rbrace. \endaligned


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 \left\lbrace a_0 \right\rbrace\cup C jest łańcuchem istotnie większym od maksymalnego w sensie inkluzji łańcucha C. To pokazuje, że \left\vert U \right\vert<\left\vert P \right\vert. Podobnie możemy uzasadnić, że również \left\vert D \right\vert<\left\vert P \right\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 \left\lbrace p \right\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.

image:End_of_proof.gif

Pokrycie antyłańcuchowe posetu \mathbf{P}=\left( X,\leq \right) 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}=\left( P,\leq \right) 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=\left\lbrace x\in P</dt><dd> p\leq x \right\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 \left\lbrace p_1 \right\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:


P=A_1\cup\ldots\cup A_h.


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.

image:End_of_proof.gif

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}=\left( P,\leq \right) 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ż \left\vert A_i \right\vert\leq s, to


\left\vert P \right\vert=\left\vert A_1 \right\vert+\ldots+\left\vert A_{r'} \right\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.

image:End_of_proof.gif
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=\left( a_1,\ldots,a_n \right) będzie ciągiem liczb rzeczywistych. Na parach postaci \left( i,a_i \right), wprowadzamy relację częściowego porządku kładąc

\left( i,a_i \right)\leq\left( j,a_j \right) 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.

image:End_of_proof.gif

Krata podzbiorów i twierdzenie Sperner'a.



Posety: \mathbf{P}_\emptyset=\left( \mathscr{P}\!\left( \emptyset \right),\subseteq \right), \mathbf{P}_{\left\lbrace a \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a \right\rbrace \right),\subseteq \right),

\mathbf{P}_{\left\lbrace a,b \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a,b \right\rbrace \right),\subseteq \right),

\mathbf{P}_{\left\lbrace a,b,c \right\rbrace}=\left( \mathscr{P}\!\left( \left\lbrace a,b,c \right\rbrace \right),\subseteq \right)

Dla dowolnego zbioru X rodzina \mathscr{P}\!\left( X \right) jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany \left( \mathscr{P}\!\left( X \right),\subseteq \right).

Rodzina Sperner'a podzbiorów zbioru X to antyłańcuch w posecie \left( \mathscr{P}\!\left( X \right),\subseteq \right).

Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu \left( \mathscr{P}\!\left( X \right),\subseteq \right). Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.

Twierdzenie 2.5 [K. Yamamoto 1954; L. D. Meshalkin 1963; D. Lubell 1966]

Niech \left\lbrace A_1,\ldots,A_m \right\rbrace będzie rodziną Spernera podzbiorów zbioru X. Wówczas


\sum_{i=1}^{m}{\left\vert X \right\vert \choose \left\vert A_i \right\vert}^{-1}\leq 1.


Dowód [D. Lubell]

Niech n=\left\vert X \right\vert. W posecie \left( \mathscr{P}\!\left( X \right),\subseteq \right) każdy maksymalny łańcuch


\emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X


musi spełniać \left\vert C_j \right\vert=j. Zbiór C_1 może być wybrany na n sposobów, z kolei C_2 na n-1 sposobów. W ogólności C_j może być wybrany na n-j+1 sposobów. Czyli łącznie jest n! różnych łańcuchów maksymalnych.

Z drugiej strony policzymy ile jest łańcuchów, w których występuje konkretny zbiór A_i z rodziny Spernera, tzn.


\emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\left\vert A_i \right\vert}=A_i \subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X


Ponieważ singleton C_1 musi zawierać się w A_i, może być wybrany na \left\vert A_i \right\vert sposobów. Tak więc C_2 może być wybrane już jedynie na \left\vert A_i \right\vert-1 sposobów i tak dalej. A zatem różnych łańcuchów postaci


\emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\left\vert A_i \right\vert}=A_i


jest \left\vert A_i \right\vert!. W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci


A_i=C_{\left\vert A_i \right\vert}\subseteq C_{\left\vert A_i \right\vert+1}\subseteq\ldots\subseteq C_n=X


jest \left( n-\left\vert A_i \right\vert \right)!. Podsumowując, liczba maksymalnych łańcuchów, w których występuje A_i wynosi \left\vert A_i \right\vert!\left( n-\left\vert A_i \right\vert \right)!.

Ponieważ \left\lbrace A_1,\ldots,A_m \right\rbrace jest antyłańcuchem, to dla i\neq j w łańcuchu nie mogą wystąpić równocześnie A_i i A_j. Zliczając teraz maksymalne łańcuchy przechodzące przez któreś A_i, możemy pominąć jakiś łańcuch maksymalny. Nie mniej jednak mamy


\sum_{i=1}^m{\left\vert A_i \right\vert!\left( n-\left\vert A_i \right\vert \right)!}\leq n!.


To w konsekwencji daje


\sum_{i=1}^{m}{\frac{1}{{n\choose\left\vert A_i \right\vert}}} =\sum_{i=1}^m{\frac{\left\vert A_i \right\vert!\left( n-\left\vert A_i \right\vert \right)!}{n!}} \leq 1.


image:End_of_proof.gif

Przykład

Oczywiście, dla ustalonego k rodzina k-elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość {n\choose k} jest maksymalna dla k=\left/n\lfloorn/2\right\rfloor, to n-elementowy podzbiór ma rodzinę Spernera o mocy {n \choose \left/n\lfloorn/2\right\rfloor}. Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.

Twierdzenie 2.6 [E. Sperner 1928]

Jeśli \mathscr{A} jest rodziną Spernera podzbiorów zbioru X, to


\left\vert \mathscr{A} \right\vert\leq{\left\vert X \right\vert\choose\left\lfloor\left\vert X \right\vert/2\right\rfloor}.


Dowód

Niech n=\left\vert X \right\vert oraz \mathscr{A}=\left\lbrace A_1,\ldots,A_m \right\rbrace. Wartość {n\choose k} jest maksymalna dla k=\left\lfloorn/2\right\rfloor. Tak więc {n\choose\left\vert A_i \right\vert}\leq{n\choose{n/2}}. Na mocy Twierdzenia 2.5 otrzymujemy:


m\frac{1}{{n \choose \left\lfloorn/2\right\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\left\vert A_i \right\vert}}}\leq 1,


skąd natychmiast


m\leq{n\choose\left\lfloorn/2\right\rfloor}.


image:End_of_proof.gif
Uwaga

W posecie \left( \mathscr{P}\!\left( X \right),\subseteq \right) dowolne dwa jego elementy A,B\in\mathscr{P}\!\left( X \right) spełniają:

  • A\cap B jest największym wspólnym ograniczeniem dolnym dla A i B,
  • A\cup B jest największym wspólnym ograniczeniem górnym dla A i B.

W takim razie dowolne dwa elementy posetu \left( \mathscr{P}\!\left( X \right),\subseteq \right) mają najmniejsze ograniczenie górne oraz największe ograniczenie dolne. Posety o tej własności nazywane są kratami.

Krata to częściowy porządek \mathbf{P}=\left( P,\leq \right), w którym dla dowolnych a,b\in P istnieją

  • kres dolny, czyli największe ograniczenie dolne wspólne dla a i b.

Kres dolny oznaczać bedziemy przez a \wedge b.

  • kres górny, czyli najmniejsze ograniczenie górne wspólne dla a i b.

Kres dolny oznaczać bedziemy przez a \vee b.

Przykład

Rozważmy zbiór liczb naturalnych \mathbb{N} oraz relacje \sqsubseteq zdefiniowaną w następujący sposób


a \sqsubseteq b\quad\textrm{wtedy i tylko wtedy, gdy}\quad a\ \textrm{dzieli}\ b\quad\textrm{dla}\ a,b\in\mathbb{N}.


Relacja \sqsubseteq jest zwrotna, antysymetryczna, i przechodnia. Tak więc para \left( \mathbb{N},\sqsubseteq \right) tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że \left( \mathbb{N},\sqsubseteq \right) jest kratą, oraz że kres dolny dwu liczb naturalnych to ich największy wspólny dzielnik, a kres ich kres górny to najmniejsza wspólna wielokrotność.