Porządki Częściowe i twierdzenie Dilworth'a

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

\( 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}=( 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:

\( \begin{align*} U=\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie ,że }p\geq a \rbrace, \\ D=\lbrace p\in P:\textrm{ istnieje }a\in A \textrm{ takie, że }p\leq a \rbrace. \end{align*} \)

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:

\( 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.

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.

Krata podzbiorów i twierdzenie Sperner'a.

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

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

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

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

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

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

Dowód [D. Lubell]

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

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

musi spełniać \( \vert C_j \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_{\vert A_i \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 \( \vert A_i \vert \) sposobów. Tak więc \( C_2 \) może być wybrane już jedynie na \( \vert A_i \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_{\vert A_i \vert}=A_i \)

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

\( A_i=C_{\vert A_i \vert}\subseteq C_{\vert A_i \vert+1}\subseteq\ldots\subseteq C_n=X \)

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

Ponieważ \( \lbrace A_1,\ldots,A_m \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{\vert A_i \vert!( n-\vert A_i \vert )!}\leq n!. \)

To w konsekwencji daje

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

Przykład

Oczywiście, dla ustalonego \( k \) rodzina \( k \)-elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość \( {n\choose k} \) jest maksymalna dla \( k=/n/2\rfloor \), to \( n \)-elementowy podzbiór ma rodzinę Spernera o mocy \( {n \choose /n/2\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

\( \vert \mathscr{A} \vert\leq{\vert X \vert\choose\lfloor\vert X \vert/2\rfloor}. \)

Dowód

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

\( m\frac{1}{{n \choose/2\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}}\leq 1, \)

skąd natychmiast

\( m\leq{n\choose/2\rfloor}. \)

Uwaga

W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) dowolne dwa jego elementy \( A,B\in\mathscr{P}\!( X ) \) 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 \( ( \mathscr{P}\!( X ),\subseteq ) \) 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}=( P,\leq ) \), 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 \( ( \mathbb{N},\sqsubseteq ) \) tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że \( ( \mathbb{N},\sqsubseteq ) \) 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ść.