Informatyka MIMUW

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ść.