Zagadnienia Mini-Maksowe w grafach

Poznane już Twierdzenie Forda-Fulkersona orzeka, że w sieciach wartość maksymalnego przepływu i przepustowości minimalnego przekroju są sobie równe. Przyjrzymy się teraz dokładniej związkom tego typu, tzn. takim, w których maksymalizacja pewnej wartości jest równoważna minimalizacji innej. Związki takie są użyteczne, gdyż poszukiwanie jednej można zastąpić poszukiwaniem drugiej, co w praktyce może okazać się łatwiejsze. Zaczniemy od bliższego przyjrzenia się skojarzeniom i bardzo mocno z nimi związanym pokryciom grafu: wierzchołkowym i krawędziowym.

Skojarzenie w grafie \( \mathbf{G}=( V,E ) \) to taki zbiór krawędzi \( M\subseteq E \), w którym żadne dwie nie są incydentne z tym samym wierzchołkiem.

Skojarzenie maksymalne to skojarzenie o maksymalnej liczności.
Liczność maksymalnego skojarzenia w grafie \( \mathbf{G} \) oznaczamy przez \( \nu( \mathbf{G} ) \).

Skojarzenie doskonałe to skojarzenie wykorzystujące wszystkie wierzchołki grafu.

Pokrycie krawędziowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego krawędzi \( E_0\subseteq E \), że każdy wierzchołek grafu \( \mathbf{G} \) jest incydentny z co najmniej jedną krawędzią w \( E_0 \).

Minimalne pokrycie krawędziowe to pokrycie krawędziowe wykorzystujące najmniejszą możliwą liczbę krawędzi. Liczbę krawędzi w minimalnym pokryciu krawędziowym oznaczamy przez \( \rho( \mathbf{G} ) \).

Pokrycie wierzchołkowe grafu \( \mathbf{G}=( V,E ) \) to taki podzbiór jego wierzchołków \( V_0\subseteq V \), że każda krawędź grafu \( \mathbf{G} \) jest incydentna z co najmniej jednym wierzchołkiem z \( V_0 \).

Minimalne pokrycie wierzchołkowe to najmniej liczne pokrycie wierzchołkowe. Liczność minimalnego pokrycia wierzchołkowego grafu \( \mathbf{G} \) oznaczamy przez \( \tau( \mathbf{G} ) \).

Zbiór niezależny w grafie \( \mathbf{G}=( V,E ) \) to taki zbiór wierzchołków \( I \), że graf indukowany \( \mathbf{G}|_I \) jest antykliką, tzn. \( {\sf E}\!(G|_I)=\emptyset \). Innymi słowy, zbiór niezależny składa się z wierzchołków niepołączonych.

Maksymalny zbiór niezależny to najbardziej liczny zbiór niezależny. Jego moc oznaczamy przez \( \alpha( \mathbf{G} ) \).

Twierdzenie 1.1 [T. Gallai 1959]

Dla grafu \( \mathbf{G} \) zachodzą:

• \( \alpha( \mathbf{G} )+\tau( \mathbf{G} )=\vert {\sf V}\!(\mathbf{G}) \vert \),

• \( \nu( \mathbf{G} )+\rho( \mathbf{G} )=\vert {\sf V}\!(\mathbf{G}) \vert \), o ile graf \( \mathbf{G} \) nie posiada punktów izolowanych.

Dowód <

Dla dowodu punktu pierwszego niech \( C_v \) będzie minimalnym pokryciem wierzchołkowym. Gdyby w zbiorze \( {\sf V}\!(\mathbf{G})- C_v \) istniały wierzchołki \( u,v \) połączone krawędzią, to taka krawędź \( uv \) nie byłaby incydentna z żadnym wierzchołkiem z \( C_v \), co przeczy temu, że \( C_v \) jest pokryciem. A zatem zbiór \( {\sf V}\!(\mathbf{G})- C_v \) jest niezależny i można go więc oszacować

\( \vert {\sf V}\!(\mathbf{G}) \vert-\tau( \mathbf{G} )=\vert {\sf V}\!(\mathbf{G})- C_v \vert\leq \alpha( \mathbf{G} ), \)

co daje \( \vert {\sf V}\!(\mathbf{G}) \vert\leq\tau( \mathbf{G} )+ \alpha( \mathbf{G} ). \) Z drugiej strony, jeśli \( I \) jest maksymalnym zbiorem niezależnym, to \( {\sf V}\!(\mathbf{G}) - I \) jest pokryciem wierzchołkowym. Tak więc

\( \tau( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) - I \vert=\vert {\sf V}\!(\mathbf{G}) \vert-\alpha( \mathbf{G} ) \)

i w konsekwencji \( \tau( \mathbf{G} )+ \alpha( \mathbf{G} )\leq\vert {\sf V}\!(\mathbf{G}) \vert. \)

Dla dowodu punktu drugiego niech \( C_e \) będzie minimalnym pokryciem krawędziowym grafu \( \mathbf{G} \). Bez trudu można zauważyć, że pokrycie takie jest lasem (bo z każdego cyklu można usunąć jakąś krawędź i reszta dalej będzie pokryciem), w którym każda składowa spójna jest gwiazdą (bo z każdej ścieżki o długości co najmniej \( 3 \) można usunąć jedną wewnętrzna krawędź). Niech więc \( C_e \) składa się z \( s \) gwiazd. Wybierzmy z każdej gwiazdy po jednej krawędzi, konstruując w ten sposób jakieś skojarzenie \( M \) o mocy \( s \). Każda gwiazda ma o jeden więcej wierzchołków niż krawędzi, tak więc \( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s \), skąd natychmiast

\( \vert {\sf V}\!(\mathbf{G}) \vert=\vert C_e \vert+s=\vert C_e \vert+\vert M \vert\leq\rho( \mathbf{G} )+\nu( \mathbf{G} ). \)

Z drugiej strony, jeśli \( M' \) jest maksymalnym skojarzeniem w \( \mathbf{G} \), czyli \( \vert M' \vert=\nu( \mathbf{G} ) \), to zbiór \( I'={\sf V}\!(\mathbf{G})- {\sf V}\!(M) \) jest zbiorem niezależnym i ma \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) elementów. Ponieważ \( \mathbf{G} \) nie ma punktów izolowanych, to każdy wierzchołek z \( I' \) jest połączony krawędzią z jakimś wierzchołkiem ze zbioru \( {\sf V}\!(M) \). Dla każdego wierzchołka \( v\in I' \) wybierzmy krawędź incydentną z \( v \). Tak powstały zbiór krawędzi w sumie z \( M \) tworzy pokrycie krawędziowe \( C_e' \) grafu \( \mathbf{G} \). W \( C_e' \) jest \( \nu( \mathbf{G} ) \) krawędzi ze skojarzenia \( M' \) oraz \( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) \) krawędzi incydentnych z elementami \( I' \). A zatem

\( \nu( \mathbf{G} )+( \vert {\sf V}\!(\mathbf{G}) \vert-2\cdot\nu( \mathbf{G} ) ) =\vert C_e' \vert\geq\rho( \mathbf{G} ), \)

i w konsekwencji \( \rho( \mathbf{G} )+\nu( \mathbf{G} )\leq \vert {\sf V}\!(\mathbf{G}) \vert \).

Twierdzenie 1.2

Jesli \( \mathbf{G} \) jest grafem prostym, to:

• minimalne w sensie inkluzji pokrycie krawędziowe \( C \) grafu \( \mathbf{G} \) jest najmniej liczne wtedy i tylko wtedy, gdy \( C \) zawiera jakieś maksymalne skojarzenie w \( \mathbf{G} \),
• maksymalne w sensie inkluzji skojarzenie \( M \) grafu \( \mathbf{G} \) jest najbardziej liczne wtedy i tylko wtedy, gdy \( M \) jest zawarte w jakimś minimalnym pokryciu krawędziowym \( \mathbf{G} \).

Dowód

Dla dowodu pierwszej równoważności zauważmy, jak w dowodzie Twierdzenia 1.1, że minimalne pokrycie \( C \) o \( \rho( \mathbf{G} ) \) krawędziach składa się z gwiazd. W każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków. Tak więc, na mocy Twierdzenia 1.1, liczba gwiazd jest równa \( \vert {\sf V}\!(\mathbf{G}) \vert-\rho( \mathbf{G} )=\nu( \mathbf{G} ) \). Wybierając teraz z każdej gwiazdy po jednej krawędzi dostaniemy ich dostatecznie dużo, by stanowiły skojarzenie maksymalne.

Dla dowodu implikacji odwrotnej znów skorzystamy z faktu, że pokrycie \( C \), jako minimalne w sensie inkluzji, składa się z gwiazd. A zatem, gdy \( C \) zawiera jakieś maksymalne skojarzenie \( M' \), to i \( M' \) musi zawierać po dokładnie jednej krawędzi z każdej gwiazdy pokrycia \( C \). Istotnie, gdyby jakaś gwiazda nie zawierała krawędzi z \( M' \), to \( M' \) nie było by maksymalne, a gdyby w gwieździe były dwie krawędzie z \( M' \), to \( M' \) nie byłoby skojarzeniem. Tak więc \( C \) składa się z \( \nu( \mathbf{G} ) \) gwiazd. Ponieważ w każdej gwieździe krawędzi jest o jedną mniej niż wierzchołków, to pokrycie \( C \) ma \( \vert {\sf V}\!(\mathbf{G}) \vert-\nu( \mathbf{G} )=\rho( \mathbf{G} ) \) krawędzi, co kończy dowód.

Analogiczny dowód punktu drugiego pozostawiamy jako ćwiczenie 4.

Warunek Hall'a na istnienie pełnych skojarzeń w grafach dwudzielnych \( \mathbf{G}=( V_1\cup V_2,E ) \) wykorzystuje funkcję \( \Phi: \mathscr{P}\!( V_1 ) \longrightarrow \mathscr{P}\!( V_2 ) \) zdefiniowaną przez \( \Phi\!(A)=\lbrace v_2\in V_2:\ v_1 v_2\in E \mbox{ \rm i } v_1\in V_1 \rbrace \). Innymi słowy, \( \Phi\!(A) \) to zbiór tych wierzchołków z \( V_2 \), które sąsiadują z przynajmniej jednym wierzchołkiem w \( A\subseteq V_1 \). Przypomnijmy poznane już (z dowodem) Twierdzenie Hall'a.

Twierdzenie 1.3 [o skojarzeniach w grafie dwudzielnym P. Hall 1935]

Niech \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Wówczas pełne skojarzenie \( V_1 \) z \( V_2 \) istnieje wtedy i tylko wtedy, gdy \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).

Twierdzenie 1.4 [D. Konig 1931]

W grafie dwudzielnym \( \mathbf{G} \) liczba wierzchołków w minimalnym pokryciu wierzchołkowym jest równa maksymalnej liczności skojarzenia, tzn.

\( \tau( \mathbf{G} )=\nu( \mathbf{G} ). \)

Dowód

Niech \( M \) będzie maksymalnym skojarzeniem, a \( C_v \) minimalnym pokryciem wierzchołkowym w grafie \( \mathbf{G} \). Każda krawędź w \( M \) jest incydentna z jakimś wierzchołkiem pokrycia \( C_v \). Ponadto, każdy wierzchołek z \( C_v \) jest incydentny z co najwyżej jedną krawędzią skojarzenia \( M \). Tak więc

\( \nu( \mathbf{G} )\leq \tau( \mathbf{G} ). \)

Dla dowodu odwrotnej nierówności zauważmy najpierw, że jeśli \( A\subseteq V_1\cap C_v \), to \( \vert A \vert \leq\vert \Phi\!(A)- C_v \vert \). Istotnie, inaczej zbiór \( (C_v\cup\Phi\!(A))- A \) byłby pokryciem wierzchołkowym o mocy istotnie mniejszej niż minimalne pokrycie \( C_v \). Tak więc Twierdzenie (Hall'a) 1.3 daje nam jakieś skojarzenie \( M_1 \) zbioru \( V_1\cap C_v \) z \( V_2- C_v \). Analogicznie otrzymamy jakieś skojarzenie \( M_2 \) zbioru \( V_2\cap C_v \) z \( V_1- C_v \). W efekcie zbiór \( M'=M_1\cup M_2 \) jest skojarzenie, wykorzystującym wszystkie punkty z \( C_v \). Ponadto, każda krawędź z \( M' \) jest incydentna z co najwyżej jednym wierzchołkiem z \( C_v \), co daje już pożądaną nierówność odwrotną

\( \tau( \mathbf{G} ) = \vert C_v \vert = \vert M' \vert \leq \nu( \mathbf{G} ). \)

Twierdzenie 1.5 [F.G.Frobenius, 1917]

Graf dwudzielny \( \mathbf{G}=( V_1\cup V_2, E ) \) ma skojarzenie doskonałe wtedy i tylko wtedy, gdy \( \vert V_1 \vert=\vert V_2 \vert \) oraz \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego podzbioru \( A \) zbioru \( V_1 \).

Dowód

Załóżmy najpierw, że \( M \) jest jakimś skojarzeniem doskonałym w grafie \( \mathbf{G} \). Oczywiście wierzchołki ze zbioru \( A\subseteq V_1 \) mogą być kojarzone tylko z własnymi sąsiadami, czyli z wierzchołkami ze zbioru \( \Phi\!(A) \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \). Ponadto z faktu, że każdy element z \( V_1 \) jest skojarzony przez \( M \) z dokładnie jednym elementem z \( V_2 \), przy czym każdy wierzchołek z \( V_2 \) jest wykorzystany, otrzymujemy \( \vert V_1 \vert=\vert V_2 \vert \).

Dla dowodu implikacji odwrotnej ustalmy jakieś minimalne pokrycie wierzchołkowe \( C_v \) grafu \( \mathbf{G} \), czyli pokrycie o \( \tau( \mathbf{G} ) \) wierzchołkach. W grafie dwudzielnym zbiór \( V_1 \) jest też pokryciem, więc \( \vert C_v \vert\leq\vert V_1 \vert \). Z drugiej strony, aby krawędzie incydentne z wierzchołkami z \( V_1- C_v \) były pokryte przez \( C_v \), zbiór \( \Phi\!(V_1- C_v) \) musi zawierać się w \( C_v \). Tak więc

\( \vert V_1- C_v \vert\leq\vert \Phi\!(V_1- C_v) \vert\leq\vert V_2\cap C_v \vert, \)

co implikuje, że

\( \vert V_1 \vert=\vert V_1- C_v \vert+\vert V_1\cap C_v \vert\leq\vert V_2\cap C_v \vert+\vert V_1\cap C_v \vert=\vert C_v \vert. \)

Twierdzenie Koniga 1.4 daje teraz

\( \nu( \mathbf{G} )=\tau( \mathbf{G} )=\vert C_v \vert=\vert V_1 \vert=\vert V_2 \vert, \)

czyli dostarcza maksymalnego skojarzenia o \( \vert V_1 \vert=\vert V_2 \vert \) krawędziach. Skojarzenie takie musi być wobec tego doskonałe.

Pokazaliśmy jak wyprowadzić Twierdzienie Frobeniusa z Twierdzenia K{o}niga, a wcześniej jak otrzymać Twierdzenie K{o}niga z Twierdzenia Hall'a. Na zakończenie wykładu, wyprowadzimy Twierdzenie Hall'a z Twierdzenia Frobeniusa, pokazując tym samym, że w istocie te trzy twierdzenia mówią to samo.

Dowód [Inny dowód Twierdzenia Hall'a 1.3]

Niech \( \mathbf{G}=( V_1\cup V_2, E ) \) będzie grafem dwudzielnym. Załóżmy najpierw, że w \( \mathbf{G} \) istnieje pełne skojarzenie \( V_1 \) z \( V_2 \). W takim razie dla dowolnego zbioru \( A\subseteq V_1 \), zbiór \( \Phi\!(A) \) zawiera \( \vert A \vert \) różnych elementów skojarzonych odpowiednio z elementami z \( A \). A zatem \( \vert A \vert \leq\vert \Phi\!(A) \vert \).

Ciekawsza jest oczywiście implikacja odwrotna. Załóżmy więc, że

\( (*) \) \( \vert A \vert \leq\vert \Phi\!(A) \vert \) dla każdego\( A\subseteq V_1 \).

W szczególności \( \vert V_1 \vert\leq\vert \Phi\!(V_1) \vert\leq \vert V_2 \vert \).

Jeśli \( \vert V_1 \vert=\vert V_2 \vert \), to Twierdzenie Frobenius'a daje natychmiast jakieś skojarzenie doskonałe, a zatem pełne. Niech więc \( \vert V_1 \vert < \vert V_2 \vert \). Do grafu \( \mathbf{G} \) dodajmy zbiór nowych wierzchołków \( W \) o mocy \( \vert V_2 \vert-\vert V_1 \vert \) łącząc je ze wszystkimi elementami \( V_2 \). Otrzymamy w ten sposób nowy graf dwudzielny \( \mathbf{G}'=( V_1'\cup V_2',E' ) \), gdzie \( V_1'=V_1\cup W \) oraz \( V_2'=V_2 \). Jeśli \( A'\subseteq V_1' \) zawiera jakiś wierzchołek z nowo dodanego \( W \), to \( \Phi\!(A')=V_2=V_2' \), co pociąga za sobą, że \( \vert A' \vert\leq\vert \Phi\!(A') \vert \). Jeżeli zaś \( A' \) jest rozłączny z \( W \), czyli \( A'\subseteq V_1 \), to \( \Phi\!(A')=\Phi\!(A')\cap \Phi\!(V_1) \), a więc na mocy \( (*) \) dostajemy, że \( \vert A' \vert \leq\vert \Phi\!(A') \vert \).

To, wraz z oczywistą równością \( \vert V_1' \vert=\vert V_2' \vert \) czyni graf \( \mathbf{G}' \) podatnym na Twierdzenie Frobenius'a. Tym samym graf \( \mathbf{G}' \) ma jakieś skojarzenie doskonałe \( M' \). Usuwając teraz ze skojarzenia \( M' \) krawędzie incydentne z wierzchołkami w \( W \) dostajemy pożądane pełne skojarzenie \( V_1 \) z \( V_2 \) w grafie \( G \).

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.

Własności podziałowe i Twierdzenie Ramsey'a

W tym wykładzie spróbujemy odpowiedzieć na niektóre pytania typu: jak bardzo musi być liczny dany zbiór, by wystąpiła w nim pożądana przez nas konfiguracja. Widzieliśmy, że na aby mieć gwarancję, że \( \mathbf{G}=( V,E ) \) jest spójny, potrzeba by miał on więcej niż \( \vert V \vert\cdot(\vert V \vert-1)/2 \) krawędzi. Najprostszym jednak warunkiem tego typu jest Zasada Szufladkowa Dirichleta i następujące jej uogólnienie.

Twierdzenie 3.1 [Uogólniona Zasada Szufladkowa Dirchlet'a]

Dla dowolnej liczby \( q\in\mathbb{N} \), jeśli \( X=X_1\cup\ldots\cup X_t \) oraz \( \vert X \vert\geq (q-1)t+1 \), to dla któregoś \( i \) mamy \( \vert X_i \vert\geq q \).

Dowód

Wykorzystując założenia twierdzenia otrzymujemy następujące oszacowanie:

\( (q-1)t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq t\cdot \max_{i=1,\ldots, t}{\vert X_i \vert}. \)

Tak więc

\( (q-1)+\frac{1}{t}=\frac{(q-1)t+1}{t}\leq\max_{i=1,\ldots, t}{\vert X_i \vert}. \)

Ponieważ moce zbiorów \( X_i \) są liczbami całkowitymi otrzymujemy, że ta maksymalna musi wynosić co najmniej \( q \).

Uogólniona Zasada Szufladkowa wymusza, że któryś składnik podziału musi mieć co najmniej \( q \) elementów. Zasadę tę można uogólnić w ten sposób, by zadając najpierw ciąg liczb naturalnych \( q_1,\ldots,q_k \), w miejsce jednej liczby \( q \), i podział \( X=X_1\cup\ldots\cup X_t \) żądać by któryś składnik \( X_i \) był co najmniej \( q_i \) elementowy. Otrzymujemy w ten sposób Zasadę Podziałową. Przy wszystkich \( q_i=q \) jest to Twierdzenie 3.1.

Twierdzenie 3.2 [Zasada podziałowa]

Niech \( q_1,\ldots,q_k \) będzie ciągiem liczb naturalnych. Jeśli

\( X=X_1\cup\ldots\cup X_t\quad\textrm{oraz}\quad\vert X \vert>( \sum_{i=1}^t{q_i} )-t, \)

to \( \vert X_i \vert\geq q_i \) dla pewnego \( i \).

Dowód

Załóżmy, wbrew tezie twierdzenia, że jakiś \( X \) o mocy \( \vert X \vert\geq( \sum_{i=1}^t{q_i} )-t+1 \) rozkłada się na sumę \( X=X_1\cup\ldots\cup X_t \), przy czym każdy składnik ma moc \( \vert X_i \vert\leq q_i-1 \). Wtedy nierówność dwu skrajnych liczb w

\( ( \sum_{i=1}^t{q_i} )-t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq \sum_{i=1}^t( q_i-1 ), \)

stoi w sprzeczności, i kończy dowód.

Można też pytać o liczbę wierzchołków w grafie wymuszających jedną z pożądanych konfiguracji.

Twierdzenie 3.3 [F.P.Ramsey 1930]

Dla dowolnej liczby \( r\in\mathbb{N} \), jeżeli tylko graf prosty \( \mathbf{G} \) posiada co najmniej \( 2^{2r-1} \) elementów, to \( \mathbf{G} \) zawiera jako podgraf indukowany klikę \( \mathcal{K}_{r} \) lub antyklikę \( \mathcal{A}_{r} \).

Dowód

Niech \( n:=\vert \mathbf{G} \vert\geq 2^{2r-1} \). Dla każdego \( x\in{\sf V}\!(\mathbf{G}) \) definiujemy dwa zbiory: odpowiednio zbiór sąsiadów wierzchołka \( x \) oraz zbiór elementów nie będących sąsiadami \( x \):

\( \begin{align*} {\sf N}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\in{\sf E}\!(\mathbf{G}) \rbrace, \\ {\sf A}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\notin{\sf E}\!(\mathbf{G}) \rbrace. \end{align*} \)

Zdefiniujemy ciąg grafów \( \mathbf{G}_0, \mathbf{G}_1, \ldots, \mathbf{G}_{2r-1} \). Niech \( \mathbf{G}_0:=\mathbf{G} \). Wybierzmy jakiś element \( x_1\in{\sf V}\!(\mathbf{G}) \) i zdefiniujmy podgraf \( \mathbf{G}_1 \) grafu \( \mathbf{G}_0=\mathbf{G} \) w następujący sposób

\( \mathbf{G}_1 = \left\{ \begin{array} {ll} {\mathbf{G}_0}|_{{\sf N}_{{\mathbf{G}_0}}\!( x_1 )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_0}\!( x_1 ) \vert\leq\vert {\sf N}_{\mathbf{G}_0}\!( x_1 ) \vert, \\ {\mathbf{G}_0}|_{{\sf A}_{\mathbf{G}_0}\!( x_1 )}, & \textrm{w przeciwnym wypadku.} \end{array} \right . \)

Zauważmy, że \( \vert {\sf V}\!(\mathbf{G}_1) \vert\geq2^{2r-2} \). Następnie wybieramy dowolny element \( x_2\in{\sf V}\!(\mathbf{G}_1) \) i analogicznie definiujemy \( \mathbf{G}_2 \). W ogólności dla \( i=1,\ldots,2r-1 \) graf \( \mathbf{G}_i \) definiujemy poprzez

\( \mathbf{G}_i = \left\{ \begin{array} {ll} {\mathbf{G}_{i-1}}|_{{\sf N}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_{i-1}}\!( x_i ) \vert\leq\vert {\sf N}_{\mathbf{G}_{i-1}}\!( x_i ) \vert, \\ {\mathbf{G}_{i-1}}|_{{\sf A}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{w przeciwnym wypadku,} \end{array} \right . \)

gdzie \( x_{i-1} \) jest dowolnie wybranym elementem ze zbioru \( {\sf V}\!(\mathbf{G}_{i-1}) \). Każdy kolejny graf zmniejszy się o co najwyżej połowę elementów, tak więc cały czas zachowana jest własność

\( \vert {\sf V}\!(\mathbf{G}_i) \vert\geq2^{2r-(i+1)}. \)

To z kolei implikuje, że dla \( i\leq 2r-1 \) zbiór \( {\sf V}\!(\mathbf{G}_i) \) jest niepusty, co pozwala zawsze na wybór kolejnych \( 2r-) \) wierzchołków \( x_1,\ldots,x_{2r-1} \) potrzebnych do zdefiniowania kolejnych grafów \( \mathbf{G}_i \). Każdy element \( x_i \) albo sąsiaduje ze wszystkimi wierzchołkami grafu \( \mathbf{G}_i \) albo też nie jest połączony krawędzią z żadnym z wierzchołków w \( \mathbf{G}_i \). Tak więc w ciągu \( x_1,\ldots,x_{2r-1} \) można wyróżnić podciąg \( x_{j_1},\ldots,x_{j_s} \) elementów pierwszego typu oraz podciąg \( x_{l_1},\ldots,x_{l_t} \) elementów drugiego typu. Element \( x_{j_1} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_1}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 2 \). Z kolei \( x_{j_2} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_2}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 3 \) i tak dalej. Zatem zbiór wierzchołków \( \lbrace x_{j_1},\ldots,x_{j_s} \rbrace \) w grafie \( \mathbf{G} \) indukuje \( s \)-elementową klikę. Analogicznie \( \mathbf{G}|_{\lbrace x_{l_1},\ldots,x_{l_t} \rbrace} \) jest \( t \)-elementową antykliką. Oczywiście \( s+t=2r-1 \). Tak więc na mocy Uogólnionej Zasady Szufladkowej Dirichlet'a otrzymujemy, że \( s\geq r \) albo \( t\geq r \), co kończy dowód.

Zauważmy, że zarówno Zasadę Podziałową (Twierdzenie 3.2), jak i Twierdzenie 3.3 można wypowiedzieć w tym samym języku. Niech \( \mathscr{P}_{r}\!( X ) \) będzie rodziną \( r \)-elementowych podzbiorów zbioru \( X \). Tak więc pokrycie \( X=X_1\cup\ldots\cup X_k \) to nic innego jak pokrycie rodziny \( \mathscr{P}_{1}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_k \), gdzie \( \mathscr{A}_i=\lbrace \lbrace x \rbrace:\ x\in X_i \rbrace \). Oznacza to, że w Zasadzie Podziałowej żądamy podzbioru \( Y\subseteq X \), dla którego istnieje \( i \), takie że \( \vert Y \vert= q_i \) oraz że dowolny singleton zawarty w \( Y \) należy do \( \mathscr{A}_i \).

Z drugiej strony graf prosty z Twierdzenia 3.3 to para \( \mathbf{G}=( V,E ) \), gdzie \( E\subseteq\mathscr{P}_{2}\!( V ) \). Daje to więc podział \( \mathscr{P}_{2}\!( V )=E\cup( \mathscr{P}_{2}\!( V )- E ) \). Żądanie \( r \)-elementowej kliki jest żądaniem \( r \)-elementowego podzbioru \( K \) zbioru \( V \) takiego, że dowolna "krawędź" pomiędzy elementami w \( K \), czyli dowolny element \( \mathscr{P}_{2}\!( K ) \), jest \( E \). Analogicznie poszukiwana antyklika jest po prostu podzbiorem \( A \) zbioru \( V \) takim, że \( \mathscr{P}_{2}\!( A )\subseteq \mathscr{P}_{2}\!( V )- E \).

Następne twierdzenie jest uogólnieniem Twierdzeń 3.1, 3.2, oraz 3.3. Warto zauważyć, że poniższe twierdzenie Ramsey'a nie podaje niestety minimalnego oszacowania na moc zbioru \( X \). Nie podamy też w tym wykładzie jego dowodu.

Twierdzenie 3.4 [F. P. Ramsey 1930]

Dla dowolnych \( r,t\in\mathbb{N} \) oraz dla dowolnego ciągu liczb naturalnych \( q_1,\ldots, q_t \) istnieje liczba \( n \) o następującej własności:

\( (*) \) Dla każdego zbioru \( X \) o co najmniej \( n \) elementach i dowolnego rozbicia

\( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t \), istnieje podzbiór \( Y \) zbioru \( X \) o co najmniej \( q_i \) elementach taki, że \( \mathscr{P}_{r}\!( Y )\subseteq \mathscr{A}_i \) przy pewnym \( i=1,\ldots,t \).

Liczba Ramseya \( {\sf R}_{r}\!( q_1,\ldots,q_t ) \) to najmniejsza taka liczba \( n\in\mathbb{N} \), dla której spełniony jest warunek \( (*) \).
Szczególnym przypadkiem jest \( {\sf R}\!( q_1,\ldots,q_t ):={\sf R}_{2}\!( q_1,\ldots,q_t ) \).

Wielu matematyków fascynowały i nadal fascynują liczby Ramsey'a. W szczególności dlatego, że bardzo mało nich wiemy. Poniższa tabela przedstawia dotychczasową wiedzę na temat liczb \( {\sf R}_{2}\!( m,n ) \). Jak widać nawet dla małych wartości \( n \) oraz \( m \), dokładne wartości liczb \( {\sf R}_{2}\!( m,n ) \) nie są znane.

\( \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline n\downarrow\ marrow & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \hline 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 3 & & 6 & 9 & 14 & 18 & 23 & 28\leq\ldots\leq29 & 36 \\ \hline 4 & & & 18 & 25\ldots\leq29 & 34\leq\ldots\leq36 & & & \\ \hline 4 & & & & 42\leq\ldots\leq55 & 57\leq\ldots\leq94 & & & \\ \hline 4 & & & & & 102\leq\ldots\leq178 & & & \\ \hline \end{array} \)

Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a \( {\sf R}\!( q_1,\ldots,q_t ) \) przedstawimy kilka twierdzeń przybliżających te liczby.

Uwaga

Wartość liczby Ramsey'a z indeksem \( r=1 \) jest opisana w Zasadzie Podziałowej (Twierdzenie 3.2). Zasadę tę można przeformułować jako:

\( {\sf R}_{1}\!( q_1,\ldots,q_t )=( \sum_{i=1}^t{q_i} )-t+1. \)

Dla liczb Ramsey'a z indeksem \( r=2 \) podamy, bez dowodu, następujące oszacowanie górne.

Twierdzenie 3.5

\( {\sf R}\!( q_1,\ldots,q_t )\leq\frac{t^{q_1+\ldots+q_t-2t+1}-1}{t-1}+1. \)

Z uwagi na Twierdzenie 3.3, ważną rolę odgrywają liczby Ramsey'a postaci \( {\sf R}_{r}\!( m,n ) \) a w szczególności \( {\sf R}\!( m,n )={\sf R}_{2}\!( m,n ) \). O nich możemy powiedzieć już trochę więcej w tym wykładzie.

Twierdzenie 3.6

Dla dowolnych \( m, n \geq 2 \) oraz \( r \geq 1 \) mamy:

\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)

Dowód

Niech \( X \) będzie zbiorem o \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \) elementach, \( x_0\in X \) i \( X'=X-\lbrace x_0 \rbrace \). Wtedy każdy podział \( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\mathscr{A}_2 \) indukuje podział \( \mathscr{P}_{r-1}\!( X' )=\mathscr{A}'_1\cup\mathscr{A}'_2 \), gdzie

\( \begin{align*} \mathscr{A}'_1 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_1\ \ & \ x_0\in A \rbrace, \\ \mathscr{A}'_2 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_2\ \ & \ x_0\in A \rbrace. \end{align*} \)

Ponieważ moc \( \vert X-\lbrace x_0 \rbrace \vert \) realizuje liczbę Ramsey'a \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) ) \), to w zbiorze \( X-\lbrace x_0 \rbrace \)

• istnieje podzbiór \( X_1\subseteq X-\lbrace x_0 \rbrace \) o mocy \( \vert X_1 \vert={\sf R}_{r}\!( m-1,n ) \), w którym dowolny podzbiór \( (r-1) \)-elementowy należy do \( \mathscr{A}'_1 \),

lub też

• istnieje podzbiór \( X_2\subseteq X-\lbrace x_0 \rbrace \) o mocy \( \vert X_2 \vert={\sf R}_{r}\!( m,n-1 ) \), w którym dowolny podzbiór \( (r-1) \)-elementowy należy do \( \mathscr{A}'_2 \).

Bez straty ogólności załóżmy, że zachodzi przypadek pierwszy. Z definicji liczb Ramsey'a oraz z faktu, że \( \vert X_1 \vert={\sf R}_{r}\!( m-1,n ) \) otrzymujemy następujące dwa przypadki, których analiza jest podobna:

• W \( X_1 \) istnieje podzbiór \( X_{11}\subseteq X_1 \), o mocy \( \vert X_{11} \vert=m-1 \), i którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_1 \).

• W \( X_1 \) istnieje podzbiór \( X_{12}\subseteq X_1 \), o mocy \( \vert X_{12} \vert=n \), i którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_2 \).

Z uwagi na symetrię przeanalizujemy jedynie pierwszy przypadek. Niech \( A\subseteq X_{11}\cup\lbrace x_0 \rbrace \) ma \( r \)-elementów. Jeśli \( x_0\not\in A \), to \( A \) zawiera się w \( X_{11} \), i co za tym idzie, \( A \) należy do \( \mathscr{A}_1 \). Jeśli zaś \( x_0\in A \), to \( A-\lbrace x_0 \rbrace \) jest \( (r-1) \)-elementowym podzbiorem zbioru \( X_1 \). A więc należy do \( \mathscr{A}'_1 \). Z definicji rodziny \( \mathscr{A}'_1 \) otrzymujemy, że i w tym przypadku \( A \) należy do \( \mathscr{A}_1 \).

W konsekwencji otrzymujemy, że w \( X \) istnieje podzbiór \( Y_1 \) (w rozpatrzonym przypadku jest to \( X_{11}\cup\lbrace x_0 \rbrace \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_1 \), lub też w \( X \) istnieje podzbiór \( Y_2 \) (w rozpatrzonym przypadku jest to \( X_{12} \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_2 \). Ponieważ zbiór \( X \) ma moc \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \), to

\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)

Twierdzenie 3.7

Dla dowolnych \( m, n \geq 2 \)

\( {\sf R}\!( m,n )\leq {{m+n-2}\choose{m-1}}. \)

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na \( n \) oraz \( m \). Dla \( n=2 \) zachodzi równość

\( {\sf R}\!( m,2 )=m={{m}\choose{1}}={{m+n-2}\choose{m- 1}}, \)

a dla \( m=2 \) zachodzi równość

\( {\sf R}\!( 2,n )=n={{n}\choose{1}}={{m+n-2}\choose{m-1}}. \)

Przejdźmy więc do przypadku, gdy \( n,m>2 \). Na mocy założenia indukcyjnego mamy:

\( {\sf R}\!( m-1,n )\leq{{m+n-3}\choose{m-2}},\quad{\sf R}\!( m,n-1 )\leq{{m+n-3}\choose{m-1}}. \)

Dla \( r=2 \) Twierdzenie 3.6 mówi, że

\( {\sf R}_{2}\!( m,n )\leq{\sf R}_{1}\!( {\sf R}_{2}\!( m-1,n ),{\sf R}_{2}\!( m,n-1 ) )+1 = {\sf R}_{2}\!( m-1,n ) + {\sf R}_{2}\!( m,n-1 ). \)

Tak więc

\( \begin{align*} {\sf R}\!( m,n ) & \leq{\sf R}\!( m-1,n ) + {\sf R}\!( m,n-1 ) \\ & \leq{{m+n-3}\choose{m-2}}+{{m+n-3}\choose{m-1}} \\ & ={{m+n-2}\choose{m-1}}, \end{align*} \)

co kończy dowód.

Przejdziemy teraz do szacowania liczb Ramsey'a od dołu. Do tego celu potrzebować będziemy następującej definicji.

Dwukolorowalna rodzina \( n \)-elementowych podzbiorów zbioru \( X \) to rodzina \( \mathscr{X}\subseteq\mathscr{P}_{n}\!( X ) \), dla której istnieje takie kolorowanie elementów zbioru \( X \) dwoma kolorami tak, by żaden zbiór \( A\in\mathscr{X} \) nie składał się z elementów tego samego koloru.
Innymi słowy, rodzina \( \mathscr{X} \) jest dwukolorowalna, jeśli istnieje podzbiór \( C\subseteq X \) taki, że

\( \emptyset\neq C \cap A \neq A\quad\textrm{dla każdego}\ A\in\mathscr{X}. \)

Twierdzenie 3.8

Niech \( n\geq 1 \) oraz \( \mathscr{X}\subseteq \mathscr{P}_{n}\!( X ) \). Jeśli \( \vert X \vert < 2^{n-1} \), to rodzina \( \mathscr{X} \) jest dwukolorowalna.

Dowód

Niech \( m:=\vert X \vert \). Policzmy pary w zbiorze

\( \mathscr{A}=\lbrace ( A,C ):\ A\in\mathscr{X} \mbox{ i } ( A\subseteq C \mbox{ albo } A\subseteq X- C ) \rbrace. \)

Liczba podzbiorów zbioru \( X \) zawierających \( A \) jest równa liczbie podzbiorów zbioru \( X \) rozłącznych z \( A \), i ponieważ \( \vert A \vert=n \), to wynosi ona \( 2^{m-n} \). Zatem

\( \vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}. \)

Niech teraz rodzina \( \mathscr{X} \) nie będzie dwukolorowalna, czyli dla każdego zbioru \( C\subseteq X \) istnieje \( A\in\mathscr{X} \) taki, że \( A\subseteq C \) albo \( A\subseteq X- C \). Tak więc par w \( \mathscr{A} \) jest co najmniej tyle co podzbiorów \( C\subseteq X \), a więc

\( 2^m\leq\vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}, \)

skąd natychmiast

\( \vert \mathscr{X} \vert\geq 2^{n-1}. \)

Twierdzenie 3.9 [P. Erd{o}s 1947]

\( {\sf R}\!( n,n )\geq n2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)

Dowód

Niech \( Y \) będzie zbiorem o \( m:={\sf R}\!( n,n ) \) elementach. Połóżmy

\( X=\mathscr{P}_{2}\!( Y ) \)
i dalej

\( \mathscr{X}=\lbrace \mathscr{P}_{2}\!( A ):\ A\in\mathscr{P}_{n}\!( Y ) \rbrace. \)

Wtedy \( \mathscr{X}\subseteq\mathscr{P}_{{n\choose2}}\!( X ) \). Ponieważ \( Y \) ma \( {\sf R}\!( n,n ) \) elementów, to rodzina \( \mathscr{X} \) nie jest dwukolorowalna, tak więc na mocy Twierdzenia 3.8 trzymujemy:

\( \vert \mathscr{X} \vert\geq 2^{{n\choose 2}-1} \)

Z kolei definicja rodziny \( \mathscr{X} \) daje \( \vert \mathscr{X} \vert={m\choose n} \), a więc

\( \frac{m^n}{n!} \geq\frac{m\cdot( m-1 )\cdot\ldots\cdot( m-n+1 )}{n\cdot( n-1 )\cdot\ldots\cdot 1} ={m\choose n} =\vert \mathscr{X} \vert \geq 2^{{n\choose 2}-1} \)

Otrzymujemy więc, że

\( m^n\geq n!\cdot2^{( n^2-n-2 )/2}, \)

co z kolei implikuje, że

\( m \geq\sqrt[n]{n!}\cdot2^{n/2}\cdot2^{-1/2}\cdot2^{-1/n} \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ). \)

Oszacowanie Sterlinga na \( n! \) daje

\( \sqrt[n]{n!} =n( \frac{\sqrt[2n]{2n}\cdot\sqrt[2n]{\pi}}{e}+o( 1 ) ) =n( \frac{1}{e}+o( 1 ) ). \)

i w konsekwencji otrzymujemy:

\( {\sf R}\!( n,n )=m \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ) \geq n\cdot2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)

Twierdzenie 3.3 ma jeszcze inne ciekawe uogólnienie, pozwalające na wyszukiwanie zadanych uprzednio podgrafów w grafie macierzystym.

Twierdzenie 3.10 [W. Deuber 1974]

Dla dowolnych dwóch grafów prostych \( \mathbf{H}_1 \) oraz \( \mathbf{H}_2 \) istnieje graf prosty \( \mathbf{G} \) taki, że jakkolwiek nie podzielimy zbioru krawędzi \( {\sf E}\!(\mathbf{G}) \) na zbiory \( E_1,E_2 \), to \( \mathbf{H}_1 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_1 ) \) lub \( \mathbf{H}_2 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_2 ) \).

Elementy teorii grup

Teoria grup

---

to jeden z działów matematyki badający własności obiektów algebraicznych zwanych grupami. Wraz z zastosowaniami stanowi on obecnie ogromną, autonomiczną dziedzinę wiedzy. Historyczne korzenie teorii to: rozwiązywanie równań algebraicznych, teoria liczb oraz geometria. Euler, Gauss, Lagrange, Abel i Galois byli pionierami badań w tej dziedzinie. W szczególności, Galois jest uważany za pierwszego matematyka, 2który powiązał teorię grup z teorią ciał.

Grupa to uporządkowana czwórka \( {\mathbf G}=(G,*,',e) \), gdzie \( G \) jest dowolnym zbiorem niepustym, \( * \) działaniem dwuargumentowym, \( ' \) jest działaniem jednoargumentowym, a \( e\in G \), przy czym, dla dowolnych \( x,y,z\in G \), spełnione sa następujące warunki:

• (łączność) \( (x*y)*z=x*(y*z) \),

• \( e*x=x*e=x \), czyli \( e \) to element neutralny grupy \( {\mathbf G} \).

• \( x*x'=x'*x=e \), czyli \( x' \) jest elementem odwrotnym do \( x \) w \( {\mathbf G} \).

Rząd grupy skończonej \( {\mathbf G}=(G,*,e) \) to liczba \( \vert G \vert \) jej elementów. Gdy grupa \( {\mathbf G} \) nie jest skończona, to mówimy, że ma rząd nieskończony.

Uwaga

Czasem w grupie nie podaje się w sposób jawny elementu neutralnego lub jednoargumentowego działania zwracającego element odwrotny. Zobaczymy, że takie postępowanie jest uprawnione, bo zarówno element neutralny jak i element odwrotny do jakiegoś \( x \), jeśli istnieje to jest jedyny.

Przykład

\( \mathbf {Z}=(\mathbb{Z},+,0) \), czyli zbiór liczb całkowitych z dodawaniem i elementem neutralnym \( 0 \), jest grupą. Rzeczywiście:

• suma dwu liczb całkowitych zawsze jest liczbą całkowitą,

• \( (a+b)+c=a+(b+c) \) dla dowolnych \( a,b,c\in\mathbb{Z} \) (łączność dodawania liczb całkowitych),

• \( 0 \) jest elementem neutralnym, gdyż \( 0+a=a+0=a \),

• \( -a \) jest elementem odwrotnym liczby \( a \), gdyż \( a+(-a)=(-a)+a=0 \).

Przykład

Dla dowolnej liczby naturalnej\( n\geq 1 \), zbiór reszt modulo \( n \) wraz z dodawaniem modulo \( n \), tzn. \( \mathbf {Z}_n=(\mathbb{Z}_n,+,0) \) jest grupą. Rzeczywiście:

• suma dwu liczb modulo \( n \) wpada do zbioru \( \mathbb{Z}_n \),

• \( (a+b)+c = a+(b+c) \) dla dowolnych \( a,b,c\in\mathbb{Z}_n \),

• \( 0 \) jest elementem neutralnym, gdyż \( 0+a=a+0=a \),

• \( n-a \) jest elementem odwrotnym liczby \( a \), gdyż \( a+(n-a)=(n-a)+a=n\equiv_n 0 \).

Przykład

\( {\mathbf S}_n=(S_n,\circ) \) jest grupą, gdzie \( S_n \) to zbiór permutacji zbioru \( \mathbb{Z}_n={\{ {0,\ldots,n-1} \} } \), a \( \circ \) to składanie permutacji. Rzeczywiście:

• złożenie dwóch permutacji \( \mathbb{Z}_n \) jest permutacją \( \mathbb{Z}_n \),

• składanie funkcji, więc i permutacji, jest łączne,

• identyczność jest elementem neutralnym przy składaniu funkcji,

• permutacja odwrotna do \( \pi \) jest elementem odwrotnym do \( \pi \) w \( {\mathbf S}_n \), gdyż \( \pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=id \).

Przykład

Gdy \( \mathbb{Z}_p^*=\mathbb{Z}_p-{\{ {0} \} }={\{ {1,\ldots,p-1} \} } \) oraz \( p \) jest liczba pierwszą, to \( {\mathbf {Z}}_p^*=(\mathbb{Z}_p^*,\cdot,1) \) jest grupą, gdzie działanie \( \cdot \) to mnożenie modulo \( p \). Rzeczywiście:

• gdy \( a,b\in\mathbb{Z}_p^* \), to oczywiście \( (ab\ {\sf mod} \ p )\in{\{ {0,\ldots,p-1} \} } \). Gdyby jednak \( ab \ {\sf mod} \ p =0 \), to \( ab=qp \) dla pewnego \( q>0 \).

Liczba \( p \) byłaby więc rozkładzie \( ab=p_1\cdot\ldots\cdot p_k \), co jest niemożliwe wobec \( p_i\leq\max(a,b) < p \).

• dla dowolnych \( a,b,c \) zachodzi

\( (ab \ {\sf mod} \ p )\cdot c \ {\sf mod} \ p =a\cdot(bc \{ {\sf mod} \ p ) \ {\sf mod} \ p . \)

• \( 1 \) jest elementem neutralnym, gdyż \( 1\cdot a=a\cdot1=a \),

• Dowolny \( a\in{\{ {1,\ldots,p-1} \} }=\mathbb{Z}_p^* \) ma element odwrotny w \( {\mathbf {Z}_p^*} \). Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.

Z pierwszości \( p \) mamy \( {\sf NWD}(a,p)=1 \) zatem istnieją \( x,y \) takie, że \( xa+yp=1 \), czyli \( xa \ {\sf mod}\ p =1 \). To oznacza, iż \( x \ {\sf mod} \ p \) jest elementem odwrotnym do \( a \) w \( {\mathbf {Z}_p^*} \).

Można też, używając Małego Twierdzenia Fermata sprawdzić, że elementem odwrotnym do \( a \) jest

• • \( a^{p-2} \), jeśli \( p>2 \),

• • \( a \), jeśli \( p=2 \)

Przykład

Rozważmy trójkąt równoboczny z poetykietowanymi wierzchołkami

oraz wybrane przekształcenia tego trójkąta pozostawiające go w tym samym miejscu płaszczyzny:

Wtedy \( ({\{ {i,p,l,x,y,z} \} },\circ, i) \) jest grupą, gdzie \( \circ \) jest składaniem przekształceń.

• Poniższa tabela pokazuje wyniki wszystkich możliwych złożeń, a tym samym pokazuje, że składanie nie wyprowadza poza zbiór

\( {\{ {i,p,l,x,y,z} \} } \).

\( \begin{array} {|c|cccccc|} \hline \circ & i & p & l & x & y & z \\ \hline i & i & p & l & x & y & z \\ p & p & l & i & y & z & x \\ l & l & i & p & z & x & y \\ x & x & z & y & i & l & p \\ y & y & x & z & p & i & l \\ z & z & y & x & l & p & i \\ \hline \end{array} \)

• Jak zawsze \( i \), będąc identycznością, jest elementem neutralnym dla składania.

• Każde z rozważanych przekształceń ma odwrotne do siebie. Odwrotnym przekształceniem do rotacji w prawo \( p \) jest oczywiście rotacja w lewo \( l \). Symetrie względem kolejnych osi są same do siebie odwrotne.

Zauważmy, że w każdym wierszu (i każdej kolumnie) występuje \( i \), skąd też można wywnioskować istnienie elementów odwrotnych.

Obserwacja 4.1 [prawo skracania]

Dla grupy \( (G,*,e) \) i \( x,y,z\in G \) mamy:

• (lewostronne) jeśli \( x*y=x*z \), to \( y=z \),

• (prawostronne) jeśli \( y*x=z*x \), to \( y=z \).

Dowód

Z uwagi na symetrię, pokażemy jedynie pierwszy punkt. Załóżmy zatem, że \( x*y=x*z \) i niech \( x' \) będzie elementem odwrotnym do \( x \). Wtedy \( y = 1*y =(x'*x)*y = x'*(x*y) = x'*(x*z) = (x'*x)*z = 1*z=z \).

Obserwacja 4.2

Jeśli \( (G,*,e) \) jest grupą i \( a,b\in G \), to równanie

\( a*x=b \)

ma dokładnie jedno rozwiązanie \( x \) w \( G \).

Dowód

Niech \( a' \) będzie elementem odwrotnym do \( a \) w \( (G,*) \). Wtedy \( x=a'*b \) jest rozwiązaniem równania, gdyż

\( a*(a'*b)=(a*a')*b=e*b=b. \)

Dla dowodu jednoznaczności załóżmy, że \( x_0 \) i \( x_1 \) są rozwiązaniami naszego równania. Wtedy mamy \( a*x_0=a*x_1 \) i z lewostronnego prawa skracania \( x_0=x_1 \).

Wniosek 4.3

Każda grupa ma dokładnie jeden element spełniający warunki elementu neutralnego oraz każdy jej element ma dokładnie jeden element odwrotny.

Dowód

Niech \( (G,*,e) \) będzie grupą i \( a\in G \). Element neutralny \( e \) jest jedynym rozwiązaniem równania \( e*x=e \). Element odwrotny do \( a \) jest jedynym rozwiązaniem \( a*x=e \).

W dalszych rozważaniach o abstrakcyjnych grupach porzucimy ornamentyczny symbol \( * \) i będziemy się posługiwać notacją multiplikatywną. Zatem dla dowolnego \( x,y\in G \), gdzie \( {\mathbf G} \) jest grupą

• \( xy \) oznacza \( x * y \),

• \( 1 \) to jedyny element neutralny grupy \( {\mathbf G} \). Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem \( 1_G \).

• \( x^{-1} \) to jedyny element odwrotny do \( x \) w \( {\mathbf G} \).

Pamietajmy, że symbol \( 1 \) w większości wypadków nie oznacza dobrze znanej liczby \( 1\in\mathbb{N} \). Podobnie nie możemy zakładać, iż działanie \( \cdot \) zachowuje prawa zwykłego mnożenia. W szczególności \( xy=yx \) zachodzi dalece nie w każdej grupie (np. nie zachodzi w grupie \( {\mathbf S}_n \) dla \( n>2 \)).

Grupa abelowa to \( {\mathbf G}=(G,\cdot \),1), w której działanie \( \cdot \) jest przemienne tzn. dla dowolnych \( x,y\in G \) mamy

\( xy=yx. \)

Nazwa grup abelowych pochodzi od nazwiska Nielsa Abela, norweskiego matematyka, w którego pracach implicite pojawia się to pojęcie.

Przykład

Grupy \( {\mathbf {Z}}_n \) i \( {\mathbf {Z}}_p^* \) są abelowe, gdyż tak dodawanie, jak i mnożenie modularne jest przemienne.

Grupa przekształceń trójkąta równobocznego \( ({\{ {i,p,l,x,y,z} \} },\circ,i) \) nie jest abelowa, gdyż np. \( xp\neq px \).

W naturalny sposób w notacji multiplikatywnej definiujemy rekurencyjnie:

Dodatnie i ujemne potęgi elementu \( x \) w grupie \( {\mathbf G}=(G,\cdot,1) \)

\( \begin{align*} x^0 & =1, \\ x^{n+1} & =x^n\cdot x, \\ x^{-n} & =(x^n)^{-1}. \end{align*} \)

Obserwacja 4.4

Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \), \( x\in G \) i \( m,n\in\mathbb{Z} \) zachodzi

\( 1^m=1,\qquad x^{m+n}=x^mx^n,\qquad x^{mn}=(x^m)^n. \)

Jeśli \( {\mathbf G} \) jest abelowa i \( x,y\in G \), to

\( (xy)^n = x^n y^n. \)

Jeśli grupa \( {\mathbf G}=(G,\cdot,1) \) ma rząd skończony, to oczywiście dla dowolnego \( x\in G \) w ciągu nieujemnych potęg: \( 1,x,x^2,x^3,\ldots \) elementy muszą zacząć się powtarzać. Załóżmy zatem, że \( m < n \) i \( x^m=x^n \). Mnożąc te równość przez \( x^{-m} \) otrzymujemy \( 1=x^{n-m} \). Udowodniliśmy zatem, iż w grupie o skończonym rzędzie każdy element w pewnej dodatniej potędze równy jest \( 1 \). Z Zasady Minimum dla każdego elementu istnieje więc najmniejsza taka dodatnia potęga.

Rząd elementu \( x\in G \) w grupie \( {\mathbf G}=(G,\cdot,1) \) o skończonym rzędzie to najmniejsza dodatnia liczba \( n \) taka, że \( x^n=1 \). Dla grup nieskończonych rząd elementu jest tak samo zdefiniowany o ile taka liczba istnieje. Jeśli nie to \( x \) ma rząd nieskończony.

Obserwacja 4.5

Dla elementu \( x \) rzędu \( m \) w grupie \( (G,\cdot,1) \) mamy \( x^n=1 \) wtedy i tylko wtedy, gdy \( m|n \).

Dowód

Jeśli \( m|n \) to \( n=q\cdot m \) dla pewnego \( q \), a zatem

\( x^n=x^{qm}=(x^{m})^q=1^q=1. \)

Na odwrót załóżmy, że \( x^n=1 \) dla pewnego \( n \). Niech \( n=qm+r \) gdzie \( 0\leq r < m \). Wtedy mamy

\( 1=x^n=x^{qm+r}=(x^m)^qx^r=1^qx^r=x^r, \)

co wraz z minimalnością \( m \) jako rzędu elementu \( x \) daje \( r=0 \), czyli \( m|n \).

Homomorfizm grup \( {\mathbf G}_0=(G_0,\cdot,1_{G_0}) \), \( {\mathbf G}_1=(G_1,\cdot,1_{G_1}) \) to dowolna funkcja \( f:G_0\to G_1 \) taka, że dla dowolnych \( x,y\in G_0 \) zachodzi

\( f(xy)=f(x)f(y). \)

Obserwacja 4.6

Dla dowolnego homomorfizmu \( f:G_0\to G_1 \) grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \) mamy:

• \( f(1_{G_0})=1_{G_1} \),

• \( f(x^{-1})=f(x)^{-1} \), dla wszystkich \( x\in G_0 \),

Dowód

Oczywiście \( f(1_{G_0})=f(1_{G_0}\cdot 1_{G_0})=f(1_{G_0})f(1_{G_0}) \). Prawo skracania w grupie \( {\mathbf G}_1 \) daje więc \( 1_{G_1}=f(1_{G_0}) \). Z kolei, gdy \( x\in G_0 \), to \( f(x)\cdot f(x^{-1})=f(xx^{-1})=f(1_{G_0})=1_{G_1} \), czyli \( f(x^{-1}) \) jest elementem odwrotnym do \( f(x) \) w \( {\mathbf G}_1 \).

Izomorfizm grup to homomorfizm, który jest bijekcją.
Grupy izomorficzne to grupy, miedzy którymi istnieje izomorfizm. Izomorficzność grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \) zapisujemy \( {\mathbf G_0}\approx{\mathbf G_1} \).

Podgrupa grupy \( {\mathbf G}=(G,\cdot,1_G) \) to taka grupa \( {\mathbf H}=(H,\cdot,1_G) \), że \( H\subseteq G \) oraz mnożenie w grupie \( {\mathbf H} \) jest restrykcją mnożenia w \( {\mathbf G} \).

Obserwacja 4.7

Dla \( \emptyset\neq H\subseteq G \), gdzie \( {\mathbf G}=(G,\cdot,1) \) jest grupą, jeśli

• \( xy\in H \) dla dowolnych \( xy\in H \),

• \( x^{-1}\in H \) dla dowolnych \( x\in H \),

to \( {\mathbf H}=(H,\cdot,1) \) jest podgrupą \( {\mathbf G} \). Ponadto jeśli \( {\mathbf G} \) ma rząd skończony, to już pierwszy punkt implikuje, iż \( {\mathbf H} \) jest podgrupą grupy \( {\mathbf G} \).

Dowód

Pierwszy punkt gwarantuje, że działanie \( \cdot \) nie wyprowadza poza zbiór \( H \). Łączność \( \cdot \) w \( H \) wynika bezpośrednio z łączności \( \cdot \) w \( G \). Drugi punkt świadczy, iż każdy element w \( H \) ma element odwrotny także w \( H \). Dla dowodu, że \( 1\in H \) skorzystamy z niepustości \( H \) i wybierzmy \( h\in H \). Wtedy, z drugiego punktu, \( h^{-1}\in H \), więc \( 1=hh^{-1}\in H \) na mocy punktu pierwszego.

Załóżmy teraz, że grupa \( {\mathbf G} \) ma rząd skończony oraz podzbiór \( H \subseteq G \) jest zamknięty na mnożenie. Wtedy oczywiście wszystkie potęgi o nieujemnych wykładnikach \( h,h^2,h^3,\ldots \) wpadają do \( H \). Ponieważ \( G \) ma rząd skończony, to rząd dowolnego elementu też jest skończony, czyli istnieje \( m \) takie, że \( h^m=1 \). Zatem \( 1\in H \) i \( h^{m-1}h=1=hh^{m-1} \), czyli \( h^{m-1}\in H \) jest elementem odwrotnym do \( h \).

Z Obserwacji 4.7 dostajemy natychmiast:

Wniosek 4.8

Przecięcie dowolnej rodziny podgrup grupy \( {\mathbf G} \) jest podgrupą \( {\mathbf G} \).

Grupy cykliczne

Podgrupa generowana przez podzbiór \( X \subseteq G \) grupy \( {\mathbf G} \), to przecięcie wszystkich podgrup \( {\mathbf G} \) zawierających zbiór \( X \). Podgrupę taką oznaczamy przez \( {\mathbf G}(X) \).
Zbiór generatorów grupy \( {\mathbf G}=(G,\cdot,1) \) to jakikolwiek zbiór \( X \subseteq G \) spełniający \( G(X)=G \).

Obserwacja 4.9

Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \) i \( \emptyset\neq X\subseteq G \)

\( G(X)={\{ {x_0\cdot\ldots\cdot x_{n-1} : n\in\mathbb{N} \mbox{ i } (x_i\in X \mbox{ lub }x_i^{-1}\in X)} \} }. \)

Dowód

Oczywiście wszystkie iloczyny postaci \( x_0\cdot\ldots\cdot x_{n-1} \) leżą w każdej podgrupie zawierającej \( X \), więc i w \( G(X) \). Nadto zbiór \( Z \) wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie, bo \( (x_0\cdot\ldots\cdot x_{n-1})^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot\ldots\cdot x_0^{-1} \). A zatem Obserwacja 4.7 gwarantuje, że \( (Z, \cdot, 1) \) jest podgrupą. Musi zatem być czynnikiem przecięcia wyznaczającego \( G(X) \), czyli \( G(X)\subseteq Z \).

Grupa cykliczna to grupa generowana zbiorem jednoelementowym.

Jeśli \( {\mathbf G} = {\mathbf G}({\{ {x} \} }) \), to \( G={\{ {x^n : n\in \mathbb{Z}} \} } \). Gdy ponadto \( {\mathbf G} \) jest skończona, to jej rząd pokrywa się z rzędem elementu generującego \( x \), czyli \( G={\{ {1,x,x^2,\ldots, x^{\vert G \vert-1}} \} } \).

Przykład

Grupa addytywna liczb całkowitych \( {\mathbf {Z}}=(\mathbb{Z},+,0) \) jest cykliczna. Rzeczywiście \( {\{ {1} \} } \) generuje te grupę:

\( \begin{array} {lrrrrrrr} \mathbb{Z}=\{\ldots, & -3, & -2, & -1, & 0, & 1, & 2, & 3,\ldots\} \\ \mathbb{Z}=\{\ldots, & -1-1-1, & -1-1, & -1, & 1-1, & 1, & 1+1, & 1+1+1,\ldots\} \end{array} \)

Czy grupa ta ma jeszcze jakiś inny jednoelemtowy zbiór generujacy?

Przykład

Dla \( n>0 \) grupa \( {\mathbf {Z}}_n=(\mathbb{Z}_n,+,0) \) jest skończoną grupą cykliczną generowaną przez \( {\{ {1} \} } \). Rzeczywiście:

\( \mathbb{Z}_n=\left\{ {1,1+1,\ldots,\underbrace{1+1+\ldots+1}_{n\ razy}} \right \}. \)

Obserwacja 4.10

Dowolne dwie grupy cykliczne tego samego rzędu są izomorficzne.

Dowód

Niech \( g_i \) będzie generatorem grupy cyklicznej \( {\mathbf G_i} \), dla \( i=0,1 \). Łatwo sprawdzić, że równość rzędów tych grup daje, iż \( g_0^k =g_0^l \) wtedy i tylko wtedy, gdy \( g_1^k =g_1^l \). A zatem \( f:G_0\ni g_0^k \mapsto g_1^k \in G_1 \) ustala izomorfizm grup \( {\mathbf G_0} \) i \( {\mathbf G_1} \).

Wniosek 4.11

Dowolna skończona grupa cykliczna rzędu \( n \) jest izomorficzna z \( \mathbb{Z}_n \). Dowolna nieskończona grupa cykliczna jest izomorficzna z \( \mathbb{Z} \).

Przykład

Dla \( n\geq3 \) rozważymy pewne grupy przekształceń \( n \)-kątów foremnych jako podgrupy grupy \( S_n \). Poetykietujmy wierzchołki \( n \)-kąta foremnego liczbami \( 0,\ldots,n-1 \). Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku, odpowiada cyklicznej permutacji \( \pi=(0,1,\ldots,n-1) \). Zastanówmy się teraz jakie elementy składają się na \( {\mathbf S}_n(\pi) \) i jaka jest ich interpretacja geometryczna.

Rząd cyklu \( n \)-elementowego jest oczywiście równy \( n \). Kolejne złożenia \( \pi,\pi^2,\pi^3,\ldots,\pi^n \) odpowiadają kolejnym obrotom \( \pi^k \) w prawo naszego wielokąta o \( \frac{360^o}{k} \), aż \( \pi^n \) przekręca go do pozycji wyjściowej (czyli jest identycznością). Zatem \( {\mathbf S}_n(\pi) \) jest grupą cykliczną rzędu \( n \), czyli z Wniosku 4.11 mamy \( {\mathbf S}_n(\pi)\approx \mathbb{Z}_n \).

Zwiększmy trochę zbiór generatorów i do obrotu w prawo dołóżmy symetrię względem jednej z \( n \) osi symetrii naszego \( n \)-kąta foremnego. W przypadku gdy \( n \) jest parzyste osie symetrii przechodzą przez środki przeciwległych boków lub naprzeciwległe wierzchołki, jeśli zaś \( n \) jest nieparzyste to osie symetrii przechodzą przez wierzchołek i środek przeciwległego do niego boku.

Permutacja odpowiadająca symetrii osiowej posiada poza cyklami wielkości \( 2 \):

• jeden cykl jednoelementowy, gdy \( n \) jest nieparzyste,

• dwa cykle jednoelementowe, gdy \( n \) jest parzyste.

Na przykład, gdy \( n \) jest parzyste oraz :

• \( \sigma \) jest symetrią względem osi przechodzącej przez bok \( [n-1,0] \), to \( \sigma \) rozkłada się na cykle:

\( \sigma=(0,n-1)(1,n-2)(2,n-3)\ldots(n/2-1,n/2+1), \)

• gdy \( \sigma \) jest symetrią względem osi przechodzącej przez wierzchołki \( 0 \) i \( (n+1)/2 \),

to \( \sigma \) rozkłada się na cykle

\( \sigma=(0)(1,n-1)(2,n-2)\ldots(n/2-1,n/2+1)( (n+1)/2 ), \)

a dla nieparzystego \( n \):

• gdy \( \sigma \) jest symetrią względem osi przechodzącej przez wierzchołek \( 0 \) i bok \( [n/2, n/2+1] \), to \( \sigma \) rozkłada się na cykle

\( \sigma=(0)(1,n-1)(2,n-2)(3,n-3)\ldots((n-1)/2,(n+1)/2). \)

Jakie elementy składają się na \( {\mathbf S}_n({\{ {\pi,\sigma} \} }) \)? Jaka jest ich interpretacja geometryczna?

Zbierzmy kilka prostych faktów:

• \( \pi^n=id \), \( \pi^{-1}=\pi^{n-1} \).

• \( \sigma \) jest inwolucją, czyli jest sama do siebie odwrotna, \( \sigma^{-1}=\sigma \).

• \( \pi\sigma\pi=\sigma \) (Zobacz rysunek)

Pokażemy tę własność jedynie dla \( n \) nieparzystych (dowód dla \( n \) parzystych znacząco się nie różni):

\( \begin{align*} \pi\sigma\pi(0) & =\pi\sigma(n-1)=\pi(1)=0=\sigma(0), \\ \pi\sigma\pi(1) & =\pi\sigma(0)=\pi(0)=n-1=\sigma(1), \\ \pi\sigma\pi(i) & =\pi\sigma(i-1)=\pi(n-i+1)=n-i=\sigma(i), \end{align*} \)

dla \( i\in{\{ {2,\ldots,n-1} \} } \).

Z Obserwacji 4.9 i naszych spostrzeżeń mamy:

\( \begin{align*} S_n({\{ {\pi,\sigma} \} }) & ={\{ {x_0\cdot\ldots\cdot x_{m-1}: m>0, x_i\in{\{ {\pi,\pi^{-1},\sigma,\sigma^{-1}} \} }} \} } \\ & ={\{ {\pi^k, \pi^k\sigma : 0 < k\leq n} \} } \end{align*} \)

Zatem podgrupa generowana przez \( {\{ {\pi,\sigma} \} } \) ma co najwyżej \( 2n \) elementów. Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne. Okazuje się, że

\( \begin{array} {ll} \pi,\pi^2,\pi^3,\ldots,\pi^n & \textrm{- to wszystkie obroty wraz z identycznością}, \\ \pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma & \textrm{- to symetrie wobec każdej z n osi symetrii n -kąta foremnego}. \end{array} \)

Grupa dihedralna \( {\mathbf D}_{n} \) to podgrupa grupy \( {\mathbf S_n} \) (dla \( n\geq3 \)) generowana przez \( {\{ {\pi,\sigma} \} } \).

Produkt grup \( {\mathbf G_0}=(G_0,\cdot,1_{G_0}) \) i \( {\mathbf G_1}=(G_1,\cdot,1_{G_1}) \) to grupa \( {\mathbf G_0}\times{\mathbf G_1}=(G_0\times G_1,\cdot,(1_{G_0},1_{G_1})) \), w której działanie \( \cdot \) zdefiniowane jest przez

\( (x,y)\cdot(z,w)=(x\cdot z,y\cdot w). \)

Weryfikację, że tak określone działanie po współrzędnych spełnia wszystkie warunki wymagane od grupy zostawiamy jako ćwiczenie.

Przykład

Rozważmy \( \mathbb{Z}_2\times\mathbb{Z}_3 \).

\( \mathbb{Z}_2\times \mathbb{Z}_3={\{ {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} \} }. \)

Zauważmy, że \( f:\mathbb{Z}_6 \to \mathbb{Z}_2\times\mathbb{Z}_3 \) zadana przez

\( f(a) = (a \ {\sf mod} \ 2 , \ a \ {\sf mod} \ 3 ) \)

definiuje izomorfizm grup \( \mathbb{Z}_6 \) i \( \mathbb{Z}_2\times\mathbb{Z}_3 \).

Czy zawsze \( \mathbb{Z}_{mn}\approx\mathbb{Z}_m\times\mathbb{Z}_n \)? Zbadajmy jeszcze jeden przykład: \( \mathbb{Z}_2\times\mathbb{Z}_4 \) i \( \mathbb{Z}_8 \). Rzędy elementów w produkcie \( \mathbb{Z}_2\times\mathbb{Z}_4 \) przedstawia tabela:

\( \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline \mathbb{Z}_2\times\mathbb{Z}_4 & (0,0) & (0,1) & (0,2) & (0,3) & (1,0) & (1,1) & (1,2) & (1,3) \\ \hline \textrm{rząd} & 1 & 4 & 2 & 4 & 2 & 4 & 2 & 4 \\ \hline \end{array} \)

A zatem grupa \( \mathbb{Z}_2\times\mathbb{Z}_4 \) nie ma elementu rzędu \( 8 \), nie może więc być izomorficzna z cykliczna grupą \( \mathbb{Z}_8 \).

Obserwacja 4.12

Jeśli \( m\perp n \), to \( \mathbb{Z}_m\times\mathbb{Z}_n \approx \mathbb{Z}_{mn} \).

Dowód

Wystarczy oczywiście pokazać, że rząd elementu \( (1,1)\in\mathbb{Z}_m\times\mathbb{Z}_n \) wynosi \( mn \), wtedy bowiem grupa \( \mathbb{Z}_m\times\mathbb{Z}_n \) będzie cykliczna i, jako \( mn \)-elementowa, musi być izomorficzna z \( \mathbb{Z}_{mn} \).

Niech więc \( r \) będzie rzędem \( (1,1) \) w grupie \( \mathbb{Z}_m\times\mathbb{Z}_n \). Licząc kolejno na obu osiach produktu dostajemy

\( \begin{align*} \underbrace{1+\ldots+1}_{r\ razy} \ {\sf mod} \ m & =r \ {\sf mod} \ m =0,\textrm{ czyli m|r,} \\ \underbrace{1+\ldots+1}_{r\ razy} \ {\sf mod} \ n & =r \ {\sf mod} \ n =0,\textrm{ czyli n|r}. \end{align*} \)

Zatem \( r \) jest najmniejszą wspólną wielokrotnością \( m \) i \( n \). Ponieważ \( m\perp n \), to

\( r={\sf NWW}(m,n)=\frac{mn}{\sf NWD}(m,n)=\frac{mn}{1}=mn.\)

Twierdzenie Lagrange'a

Zajmiemy się teraz możliwymi rzędami podgrup grupy skończonej. Z rozważań tej części wykładu dowiemy się, że jeśli \( {\mathbf H} \) jest podgrupą skończonej grupy \( {\mathbf G} \), to rząd \( {\mathbf H} \) dzieli rząd \( {\mathbf G} \). Zwracamy jednak uwagę, iż to nie oznacza, że grupa \( {\mathbf G} \) ma podgrupy o rzędzie będącym jakimkolwiek dzielnikiem rzędu grupy \( {\mathbf G} \).

Przykład

Niech \( {\mathbf A}_4 \) będzie podgrupą grupy \( {\mathbf S}_4 \) składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy \( \vert A_4\vert=12 \), ale grupa \( {\mathbf A}_4 \) nie ma podgrup rzędu \( 4 \).

Lewa warstwa \( gH \) podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) względem elementu \( g\in G \) to zbiór

\( gH={\{ {gh : h\in H} \} }. \)

Prawa warstwa \( Hg \) podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) względem elementu \( g\in G \) to zbiór

\( Hg={\{ {hg : h\in H} \} }. \)

Skoncentrujemy się teraz na lewych warstwach. Oczywiście wszystkie rozumowania można powtórzyć dla warstw prawych

Przykład

Niech \( {\mathbf D}_4=({\{ {\pi,\ldots,\pi^4,\pi\sigma,\ldots,\pi^4\sigma} \} },\circ) \) będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną \( {\mathbf C}_4=({\{ {\pi,\pi^2,\pi^3,\pi^4} \} },\circ) \). Niech \( \sigma \) będzie symetrią osiową. Zauważmy, że elementy lewej warstwy

\( \sigma C_4={\{ {\sigma\pi,\sigma\pi^2,\sigma\pi^3,\sigma\pi^4} \} }. \)

wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw \( \pi C_4 \), \( \pi^2 C_4 \) oraz \( \sigma\pi^2 C_4 \).

Zauważmy, że warstwa \( eH \) elementu neutralnego \( e \), to podgrupa \( H \). Nastepna obserwacja orzeka, że wszystkie warstwy lewo- i prawo-stronne są równoliczne.

Obserwacja 4.13

Jeśli \( {\mathbf H} \) jest skończoną podgrupą grupy \( {\mathbf G} \) i \( g\in G \), to \( \vert=\vert = \vert \).

Dowód

Niech \( H={\{ {h_0,\ldots,h_{m-1}} \} } \) i załóżmy, że \( gh_i=gh_j \). Wtedy z prawa skracania mamy \( h_i=h_j \). Zatem elementy \( gh_0,gh_1,\cdots,gh_{m-1} \) są parami różne i zbiór

\( gH={\{ {gh_0,gh_1,\cdots,gh_{m-1}} \} }, \)

ma dokładnie \( m \) elementów.

Obserwacja 4.14

Dla dowolnej podgrupy \( {\mathbf H} \) grupy \( {\mathbf G} \) i \( g_0,g_1\in G \) lewe warstwy \( g_0 H \), \( g_1H \) są albo identyczne albo rozłączne.

Dowód

Pokażemy, że jeśli \( g_0 H \) i \( g_1 H \) mają jakiś wspólny element to są one identyczne. Załóżmy zatem, że \( x\in g_0 H \cap g_1 H \), czyli \( g_0 h_0 =x= g_1 h_1 \) dla pewnych \( h_0,h_1\in H \). Wtedy \( g_0=g_1 h_1 h_0^{-1} \in g_1H \). Dla dowodu inkluzji \( g_0 H \subseteq g_1 H \), niech \( y\in g_0 H \), czyli \( y=g_0h \) dla pewnego \( h\in H \). Wtedy

\( y=g_0 h=g_1 h_1 h_0^{-1} h, \)

co wobec \( h_1,h_0^{-1},h\in H \) daje \( y\in g_1H \).

Twierdzenie 4.15[Lagrange'a]

Dla dowolnej podgrupy \( {\mathbf H} \) skończonej grupy \( {\mathbf G} \), rząd \( {\mathbf H} \) dzieli rząd \( {\mathbf G} \).

Dowód

Niech \( {\mathbf H}=({\{ {h_0,\ldots,h_{m-1}} \} },\cdot,1) \) oraz \( {\mathbf G}=({\{ {g_0,\ldots,g_{n-1}} \} },\cdot,1) \). Ponieważ:

• każdy \( g_i \) jest we własnej warstwie \( g_iH \), gdyż \( g_i\cdot1\in g_iH \),

• \( _i H \vert=\vert \) dla dowolnego \( i \),

• lewe warstwy \( g_iH \), \( g_jH \) są albo identyczne albo rozłączne,

to lewe warstwy \( g_0H,g_1H,\ldots,g_{n-1}H \) tworzą podział zbioru \( G={\{ {g_0,g_1\ldots,g_{n-1}} \} } \) na równoliczne bloki wielkości \( m \), skąd natychmiast \( m|n \).

Wniosek 4.16

Niech \( {\mathbf G}=(G,\cdot,1) \) będzie grupą rzędu \( n \). Wtedy dla \( g \in G \) mamy:

• rząd elementu \( g \) dzieli \( n \),

• \( g^n=1 \).

Dowód

Niech \( r \) będzie rzędem elementu \( g\in G \). Wtedy \( r \) jest rzędem podgrupy cyklicznej \( {\mathbf G}(g) = ({\{ {g,g^2,\ldots,g^r} \} },\cdot,1) \). Z Twierdzenia Lagrange'a \( r \), czyli rząd tej podgrupy cyklicznej, dzieli \( n \). Skoro teraz \( n=kr \) to oczywiście \( x^n= x^{kr} = (x^r)^k = 1^k =1 \)

Wniosek 4.17

Każda grupa \( {\mathbf G} \) której rząd jest liczbą pierwszą \( p \) jest cykliczna i izomorficzna z \( \mathbb{Z}_p \).

Dowód

Ponieważ \( p>1 \), to w \( G \) jest jakiś element \( g\neq1 \). Wtedy rząd \( g \) jest większy od \( 1 \) i dzieli \( p \), więc musi wynosić \( p \). To oznacza zaś, iż \( g \) generuje grupę \( {\mathbf G} \), czyli \( {\mathbf G} \) jest cykliczna. Reszta wynika już z Wniosku 4.11.

Obserwacja 4.18

Dla dowolnej grupy \( {\mathbf G}=(G,\cdot,1) \) rzędu \( n\geq 2 \) następujące warunki są równoważne:

1. \( {\mathbf G} \) jest grupa cykliczną,

2. dla każdego \( d|n \), grupa \( {\mathbf G} \) ma dokładnie \( d \) elementów \( x\in G \) takich, że \( x^d=1 \),

3. dla każdego \( d|n \), grupa \( {\mathbf G} \) ma dokładnie \( \varphi(d) \) elementów rzędu \( d \).

Dowód

Dla dowodu implikacji (1 \( \Rightarrow \) 2) załóżmy że grupa \( {\mathbf G} \) jest cykliczna i generowana przez \( g \). Niech \( d \) będzie dzielnikiem \( n \), czyli \( n=dq \) dla pewnego \( q \). Elementy

\( 1,g^q,g^{2q},\ldots,g^{(d-1)q} \)

są parami różne (bo \( g \) ma rząd \( n=dq \)) oraz wszystkie spełniają równanie \( x^d=1 \), gdyż

\( (g^{iq})^d=(g^{dq})^i=1^i=1. \)

Zatem elementów \( x\in G \) spełniających \( x^d=1 \) jest co najmniej \( d \). Załóżmy teraz, że pewien \( y\in G \) spełnia \( y^d=1 \). Ponieważ \( g \) generuje \( {\mathbf G} \), mamy \( y=g^k \) dla pewnego \( k \), skąd \( g^{kd}=y^d=1 \). Z Obserwacji 4.5 mamy \( n|kd \), czyli \( kd=fn=fdq \) i \( k=fq \) dla pewnego \( f \). Zatem \( y=g^{k}=g^{fq} \) znajduje się na naszej liście rozwiązań równania \( x^d=1 \). To dowodzi, że elementów \( x\in G \) spełniających \( x^d=1 \) jest dokładnie \( d \).

Dla dowodu implikacji (2 \( \Rightarrow \) 3) przypomnijmy, za Obserwacją 4.5, że element \( x \) rzędu \( r \) spełnia \( x^d=1 \) wtedy i tylko wtedy, gdy \( r|d \). A zatem założenie 2 daje

\( \displaystyle d=\sum_{r|d}f(r), \)

gdzie \( f(r) \) to liczba elementów rzędu \( r \) spełniających \( x^d \)=1. Wzór inwersyjny Mobiusa daje teraz

\( \displaystyle f(d)=\sum_{r|d}\mu(r)\frac{d}{r}. \)

Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa, tzn. \( \displaystyle \varphi(d)=\sum_{r|d}\mu(r)\frac{d}{f} \), mamy \( f(d)=\varphi(d) \).

Wreszcie, dla dowodu ostatniej implikacji (3 \( \Rightarrow \) 1) zauważmy najpierw, że zawsze \( \varphi(n)\geq 1 \). To oczywiście daje, że istnieje co najmniej jeden element rzędu \( n \) w \( {\mathbf G} \). Element ten generuje więc cały zbiór \( G \), stąd \( {\mathbf G} \) jest cykliczna.

Przykład

Zbadajmy rzędy elementów grupy cyklicznej \( \mathbb{Z}_{12} \).

\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline 1 & 12 & 6 & 4 & 3 & 12 & 2 & 12 & 3 & 4 & 6 & 12 \\ \hline \end{array} \)

• dzielniki liczby \( 12 \) to \( 1,2,3,4,6,12 \).

• liczba elementów rzędu \( d \) dla kolejnych dzielników \( d|12 \)

\( \begin{array} {|c|c|c|c|c|c|c|} \hline \textrm{dzielnik d liczby {12}} & 1 & 2 & 3 & 4 & 6 & 12 \\ \hline \textrm{liczba elementów rzędu {d}} & 1 & 1 & 2 & 2 & 2 & 4 \\ \hline \end{array} \)

• \( \varphi(1)=1 \), \( \varphi(2)=1 \), \( \varphi(3)=2 \), \( \varphi(4)=2 \), \( \varphi(6)=2 \), \( \varphi(12)=4 \).

Zastosowania teorii grup w zliczaniu

Kolorowanie zbioru \( X \) to funkcja

\( \omega:X\longrightarrow K, \)

gdzie \( K \) jest zbiorem kolorów.

Przykład

Rozważmy kolorowania naszyjnika złożonego z pięciu identycznych koralików \( k_0,k_1,k_2,k_3,k_4 \). Koraliki te mają takie same kształty i nie można ich rozróżnić. Możemy zatem zauważyć, że z jednego kolorowania \( \omega_{0} \) da się utworzyć inne kolorowanie, nieodróżnialne od pierwszego, np. przez cykliczną zmianę numeracji koralików: \( \omega_{1}\!( k_i )=\omega_{0}\!( k_{( i-1\ mod\ 5 )} ) \) jest nieodróżnialne od kolorowania \( \omega_{0}\!( k_i ) \). Przekształcenie indeksów \( i-1\ mod\ 5 \) jest równoważne z obrotem o \( 72^{\circ} \).

W ten sposób dostajemy \( 5 \) kolorowań naszego naszyjnika. Ale, naszyjnik można też odwracać w rękach, lub - co na jedno wychodzi - spojrzeć na niego z drugiej strony. Mamy więc dodatkowe \( 5 \) kolorowań naszego naszyjnika.

Zauważmy, ze w istocie każde \( 10 \) z kolorowań możemy otrzymać z innego poprzez przekształcenie naszyjnika (pięciokąta) przez jakąś symetrię. Zbiór zmian ułożeń naszyjnika (permutacje jego koralików) wraz ze składaniem tych zmian (permutacji) tworzy więc grupę (w tym przypadku znaną nam już grupę dihedralną \( {\mathbf D}_5 \) symetrii pięciokąta. W wykładzie tym poznamy metody zliczania tych kolorowań, które są odróżnialne.

G-zbiór to para \( ( {\mathbf G},X ) \), gdzie

• \( X \) jest zbiorem skończonym,

• \( {\mathbf G}=( G,\circ ) \) jest grupą permutacji zbioru \( X \), tzn. \( G \) jest zamkniętym na składanie zbiorem permutacji zbioru \( X \).

Czasem, dla G-zbioru \( ( {\mathbf G},X ) \) mówimy, ze grupa \( {\mathbf G} \) działa na zbiorze \( X \).

Przykład

Rozważmy kwadrat o wierzchołkach \( v_0, v_1, v_2, v_3 \) oraz \( 4 \) permutacje jego wierzchołków powstałe przez: odbicia względem przekątnych i obrót o \( 180^\circ \), tak jak zostało to pokazane na rysunku.

Każde przedstawione przekształcenie geometryczne wyznacza jednoznacznie permutację zbioru indeksów wierzchołków kwadratu \( X_□=\lbrace 0,1,2,3 \rbrace \). Tak więc zbiór permutacji odpowiadających przekształceniom to \( G_□=\lbrace id,g_1,g_2,g_3 \rbrace \). Przekształcenia \( g_i \) można składać. Na przykład \( g_1\circ g_2 \) tworzy obrót o \( 180^{\circ} \) stopni, a więc \( g_3 \). Para \( ( G_□, \circ ) \) tworzy grupę, więc \( ( G_□, X_□ ) \) jest przykładem G-zbioru, który jest opisany przez poniższe tabelki:

\( \begin{array} {|c||c|c|c|c|} \hline j & 1 & 2 & 3 & 4 \\ \hline\hline id(j) & 0 & 1 & 2 & 3 \\ \hline g_1(j) & 0 & 2 & 1 & 3 \\ \hline g_2(j) & 3 & 1 & 2 & 0 \\ \hline g_3(j) & 3 & 2 & 1 & 0 \\ \hline \end{array} \quad\quad\quad\quad\quad \begin{array} {|c||c|c|c|c|} \hline g_i\circ g_j & id & g_1 & g_2 & g_3 \\ \hline\hline id & id & g_1 & g_2 & g_3 \\ \hline g_1 & g_1 & id & g_3 & g_2 \\ \hline g_2 & g_2 & g_3 & id & g_1 \\ \hline g_3 & g_3 & g_2 & g_1 & id \\ \hline \end{array} \)

Innymi słowy, grupa permutacji \( {\mathbf G}_□ \) działa na zbiorze \( X_□ \).

Orbita \( Gx \) elementu \( x \in X \) w G-zbiorze \( ( G,X ) \) to zbiór tych elementów zbioru \( X \), które są postaci \( g\!( x ) \) dla pewnego \( g\in G \), tzn.

\( Gx=\lbrace g\!( x )\in X: g\in G \rbrace. \)

Stabilizator \( G_x \) elementu \( x\in X \) w G-zbiorze \( ( G,X ) \) to zbiór tych permutacji z \( G \), które nie ruszają \( x \) z miejsca, tzn.

\( G_x=\lbrace g\in G:\ g\!( x )=x \rbrace. \)

Ponadto zbiór permutacji przeprowadzających \( x\in X \) w \( y\in X \) oznaczamy przez

\( G( x \to y )=\lbrace g\in G:\ g\!( x )=y \rbrace \)

Przykład

Dla grupy \( G_□ \) permutacji kwadratu z rysunku, orbita oraz stabilizator elementu \( 0 \) mają postać

\( G_□0=\lbrace 0,3 \rbrace \quad\quad\quad\quad G_{□, 0}=\lbrace id,g_1 \rbrace. \)

Mnożąc liczności obu tych zbiorów otrzymujemy liczbę elementów grupy \( G_□ \), czyli innymi słowy \( \vert G_□ 0 \vert\cdot\vert G_{□, 0} \vert=\vert G_□ \vert. \)

Przypadek? Nie sądzę.

Twierdzenie 5.2

Dla G-zbioru \( ( G,X ) \) oraz \( x \in X \) zachodzi

\( \vert Gx \vert\cdot\vert G_x \vert=\vert G \vert. \)

Dowód

Pokażemy, że istnieje wzajemnie jednoznaczna odpowiedniość między elementami orbity \( Gx \) a warstwami \( G \) względem stabilizatora \( G_x \). Teza twierdzenia wyniknie wtedy natychmiast z twierdzenia Lagrange'a.

Mamy \( g_1(x) = g_2(x) \Leftrightarrow g_1^{-1}g_2(x) = x \Leftrightarrow g_1^{-1}g_2(x)\in G_x \Leftrightarrow g_2\in g_1G_x.\)

Zbiór punktów stałych permutacji \( g\in G \) to

\( {\sf Fix}( g )=\lbrace x\in X:\ g\!( x )=x \rbrace. \)

Twierdzenie 5.4

Dla G-zbioru \( ( G,X ) \) oraz funkcji \( f \) stałej na każdej orbicie \( Gx \) zachodzi

\( \displaystyle \sum_{x\in D}f\!( x )=\frac{1}{\vert G \vert}\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \)

gdzie \( D\subseteq X \) jest zbiorem reprezentantów orbit, tzn. \( \vert D \cap Gx \vert=1 \) dla dowolnego \( x\in X \).

Dowód

Policzymy, na dwa różne sposoby, sumę

\( \displaystyle \sum_{( g,x )\in B}f\!( x ) \)

gdzie \( B=\lbrace ( g,x ):g\!( x )=x \rbrace \). Zliczając najpierw po \(g\in G\), a potem po \(x\in {\sf Fix}( g )\), dostajemy sumę
\[\sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ), \]
natomiast zliczając najpierw po \(x\in X\), a potem po \(g\in G_x\), dostajemy sumę
\[\sum_{x\in X}\vert G_x \vert f\!( x ) = \vert G \vert\sum_{x\in X}\frac{f\!( x )}{\vert Gx \vert}.\]
Każdy element orbity \( Gx\) wnosi do sumy taką samą wartość \(\frac{f\!( x )}{\vert Gx \vert}\) (bo \(f\) jest stała na każdej orbicie), zatem cała orbita \( Gx\) wnosi \( f(x)\), czyli ostatecznie \( \sum_{g\in G} \sum_{x\in {\sf Fix}( g )} f\!( x ) = \vert G\vert \sum_{x\in D}f\!( x )\).

Wniosek 5.5

Liczba orbit w G-zbiorze \( ( G,X ) \) wynosi

\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \vert. \)

Permutacje na zbiorze kolorowań. Niech \( ( G,X ) \) będzie G-zbiorem, a \( A \) zbiorem kolorowań zbioru \( X \). Każda permutacja \( g\in G \) wyznacza permutację \( \widehat{g}:A\longrightarrow A \) kolorowań ze zbioru \( A \) poprzez

\( ( \widehat{g}\!( \omega ) )\!( x ) =\omega\!( g\!( x ) )\quad\textrm{dla dowolnych}\ \omega\in A\ \textrm{i}\ x\in X. \)

Obserwacja 5.6

Niech \( ( G,X ) \) będzie G-zbiorem, a \( A \) zbiorem kolorowań zbioru \( X \). Dla \( \widehat{G} = \lbrace \widehat{g}: g \in G \rbrace \) zachodzi:

• Para \( ( \widehat{G},\circ ) \) tworzy grupę, gdzie \( \circ \) jest składaniem permutacji.

• Funkcja \( \widehat{\cdot}:G\longrightarrow\widehat{G} \) jest izomorfizmem grup \( ( G,\circ ) \) oraz \( ( \widehat{G},\circ ) \).

• \( \vert G \vert=\vert \widehat{G} \vert \).

• \( ( \widehat{G},A ) \) jest G-zbiorem.

Izomorficzne kolorowania. Kolorowania \( \omega_{0} \) i \( \omega_{1} \) zbioru \( X \) są izomorficzne względem działania grupy \( G \) na zbiorze \( X \), gdy istnieje permutacja \( g\in G \) taka, że \( \widehat{g}\!( \omega_{0} ) = \omega_{1} \), czyli

\( \displaystyle \omega_{0}\!( g\!( x ) )=\omega_{1}\!( x )\quad\textrm{dla dowolnego}\ x\in X. \)

Przykład

Kolorowania z rysunku są izomorficzne względem działania grupy \( {\mathbf D}_5 \) wszystkich zmian ustawień \( 5 \)-elementowego naszyjnika.

Indeks permutacji \( g:X\longrightarrow X \) to funkcja \( n \) zmiennych

\( \zeta_{g}( x_1,\ldots,x_n ) =x_1^{\alpha_1}\cdot x_2^{\alpha_2}\cdot\ldots\cdot x_n^{\alpha_n}, \)

gdzie

• \( n \) to liczność zbioru \( X \),

• \( \alpha_i \) to liczba \( i \)-elementowych cykli permutacji \( g \),

dla \( i=1,2,\ldots,n \).

Indeks grupy \( G \) to funkcja \( n \) zmiennych

\( \displaystyle \zeta_{G}( x_1,\ldots,x_n )=\frac{1}{\vert G \vert}\sum_{g\in G}\zeta_{g}( x_1,\ldots,x_n ). \)

Przykład

Niech \( ( G_t,\circ ) \) będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w \( 3 \)-wymiarowej przestrzeni.

Obroty czworościanu mają więc następujące indeksy \( \zeta_{g}( x_1,x_2,\ldots,x_8 ) \), w zależności od rozkładu na cykle:

• \( x_1^4 \) - jedyny taki obrót z jednoelementowymi cyklami to oczywiście \( id=( 0 )\!( 1 )\!( 2 )\!( 3 ) \).

• \( x_1x_3 \) - obroty o \( 120^{\circ} \) względem prostej przechodzącej przez jeden z wierzchołków i środek przeciwległej ściany. W grupie \( G_t \) jest ich \( 8 \). Przykładem permutacji o indeksie \( x_1x_3 \) jest \( ( 0 )\!( 123 ) \), która odpowiada przekształceniu przedstawionym na rysunku.

• \( x_2^2 \) - obroty o \( 180^{\circ} \) względem osi przechodzącej przez środki przeciwległych krawędzi.

W sumie są \( 3 \) takie obroty. Permutacją o indeksie \( x_2^2 \) jest na przykład \( ( 03 )\!( 12 ) \) i odpowiada ona przekształceniu przedstawionym na rysunku.

Indeks całej grupy obrotów czworościanu to zatem:

\( \zeta_{G_t}( x_1,x_2,x_3,x_4 )=\frac{1}{12}( x_1^4+8x_1x_3+3x_2^2 ). \)

Twierdzenie 5.7

Liczba nieizomorficznych kolorowań zbioru \( X \) za pomocą \( k \) barw wynosi

\( \zeta_{G}( k,k,\ldots,k ), \)

gdzie \( G \) jest grupą możliwych permutacji elementów \( X \).

Dowód

Niech \( A \) będzie zbiorem wszystkich kolorowań \( k \) barwami zbioru \( X \). Szukana liczba nieizomorficznych kolorowań jest równa liczbie orbit G-zbioru \( ( \widehat{G},A ) \) i, na mocy Wniosku 5.5 oraz Obserwacji 5.6, wynosi:

\( \displaystyle \frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in\widehat{G}}\vert {\sf Fix}( \widehat{g} ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( {g} ) \vert. \)

Pozostaje więc policzyć liczbę punktów stałych każdej z permutacji \( \widehat{g} \) . Jeśli \( \omega \) jest punktem stałym permutacji \( \widehat{g} \), a \( ( i_1,i_2,\ldots,i_l ) \) jest cyklem tej permutacji, to

\( \displaystyle \omega\!( i_{j+1} ) =\omega\!( g\!( i_j ) ) =( \widehat{g}\!( \omega ) )\!( i_j )=\omega\!( i_j ). \)

A zatem wszystkie elementy \( i_j \) tego cyklu są pokolorowane na ten sam kolor. Niech teraz permutacja \( g \) rozkłada się na \( m \) cykli. Ponieważ elementy każdego cyklu muszą być jednobarwne, a wszystkich możliwych do wykorzystania barw jest \( k \), to liczba możliwych kolorowań elementów \( X \) wynosi \( \vert {\sf Fix}( g ) \vert=k^m \). Z drugiej strony

\( \displaystyle \zeta_{g}( k,k,\ldots,k ) =k^{\alpha_1}\cdot k^{\alpha_2}\cdot\ldots\cdot k^{\alpha_s}, \)

gdzie \( \alpha_i \) jest liczbą cykli \( i \) elementowych. Ale oczywiście \( \alpha_1+\alpha_2+\ldots+\alpha_s=m \), skąd \( \vert {\sf Fix}( g ) \vert=\zeta_{g}( k,k,\ldots,k ) \). Liczba nieizomorficznych kolorowań jest więc równa

\( \displaystyle \frac{1}{\vert G \vert}\sum_{g\in G}\vert {\sf Fix}( g ) \vert =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( k,k,\ldots,k ) =\zeta_{G}( k,k,\ldots,k ). \)

Przykład

Niech \( ( G_t,\circ ) \) będzie grupą wszystkich obrotów czworościanu foremnego (przedstawionego na rysunku) w \( 3 \)-wymiarowej przestrzeni. Wiemy już, że indeks grupy \( G_t \) wynosi

\( \zeta_{G_t}( x_1,x_2,x_3,x_4 )=\frac{1}{12}( x_1^4+8x_1x_3+3x_2^2 ). \)

Aby zliczyć wszystkie, nieizomorficzne względem obrotów, kolorowania wierzchołków czworościanu na \( 2 \) kolory wystarczy, wobec Twierdzenia 5.7, policzyć wartość

\( \zeta_{G_t}( 2,2,2,2 )=5. \)

Faktycznie. Jedynymi kolorowaniami nieizomorficznymi względem obrotów są te, przedstawione na rysunku.

Wskaźnik kolorowania \( \omega:X\longrightarrow K \), dla zbioru kolorów \( K=\lbrace 1,2,\ldots,k \rbrace \) to

\( {\sf ind}( \omega )=x_1^{n_1}\cdot x_2^{n_2}\cdot\ldots\cdot x_k^{n_k}, \)

gdzie \( n_i \) to liczba elementów ze zbioru \( X \) pokolorowanych przez \( \omega \) na kolor \( i \).
Ponadto dla zbioru kolorowań \( A \) definiuje się funkcję tworzącą postaci

\( \displaystyle {\sf U}_{A}( x_1,x_2,\ldots,x_k )=\sum_{\omega\in A}{\sf ind}( \omega ) =\sum_{\omega\in A}x_1^{n_1( \omega )}\cdot x_2^{n_2( \omega )}\cdot\ldots\cdot x_k^{n_k( \omega )}. \)

Twierdzenie 5.8

Dla podziału zbioru \( X=Y_1\cup Y_2\cup\ldots\cup Y_l \) mamy

\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k )=\prod_{i=1}^l( x_1^{\vert Y_i \vert} +x_2^{\vert Y_i \vert} +\ldots+ x_k^{\vert Y_i \vert} ), \)

gdzie \( D \) jest zbiorem kolorowań stałych na zbiorach \( Y_i \).

Dowód

Niech \( \vert Y_i \vert=m_i \). Iloczyn

\( \displaystyle \prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} ) \)

jest sumą jednomianów postaci \( \beta x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Aby przeanalizować te jednomiany zauważmy, że mnożąc po jednym składniku \( x_j^{m_i} \) z każdego czynnika iloczynu, otrzymamy jednomian postaci \( x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Wartość \( \beta \) jest więc równa wszystkim możliwym iloczynom \( x_{j_1}^{m_1}\ x_{j_2}^{m_2}\ldots x_{j_l}^{m_l} \) dającym \( x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \). Porządkując składniki \( x_{j_i} \) otrzymujemy, że \( \beta \) jest liczbą wszystkich zestawów sum postaci

\( \begin{align*} \alpha_1 & =m_{i_{1,1}}+\ldots+m_{i_{1,{s_1}}} \\ \alpha_2 & =m_{i_{2,1}}+m_{i_{2,2}}+\ldots+m_{i_{2,{s_2}}} \\ & \cdots & \\ \alpha_k & =m_{i_{k,1}}+\ldots+m_{i_{k,{s_k}}}. \end{align*} \)

Każdy taki zestaw sum można utożsamić z kolorowaniem, które przyporządkowuje elementom z \( Y_{i_{1,1}}\cup\ldots\cup Y_{i_{1,{s_1}}} \) pierwszą barwę, elementom z \( Y_{i_{2,1}}\cup Y_{i_{2,2}}\cup\ldots\cup Y_{i_{2,{s_2}}} \) kolejną barwę, itd... Otrzymujemy w ten sposób, że \( \beta \) jest liczbą kolorowań stałych na każdym ze zbiorów \( Y_i \). Kolorowania te używają \( \alpha_1 \) razy pierwszej barwy, \( \alpha_2 \) razy drugiej barwy, itd..., czyli jednomian \( \beta x_1^{\alpha_1}x_2^{\alpha_2}\ldots x_k^{\alpha_k} \) jest składnikiem w sumie powstałej z iloczynu \( {\sf U}_{D}( x_1,x_2,\ldots,x_k ) \) przez wymnożenie wszystkich czynników.

Twierdzenie 5.9 [G. Pólya 1935]

Niech \( \vert X \vert=n \) a \( D \) będzie zbiorem wszystkich nieizomorficznych, ze względu na działanie grupy \( G \) na zbiorze \( X \), kolorowań zbioru \( X \) za pomocą \( k \) barw. Wtedy funkcja tworząca \( {\sf U}_{D} \) jest postaci

\( {\sf U}_{D}( x_1,x_2,\ldots,x_k )=\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ), \)

gdzie

\( \sigma_i=x_1^i+x_2^i+\ldots+x_k^i. \)

Dowód

Zbiór \( D \) jest zbiorem reprezentantów orbit G-zbioru \( ( \widehat{G},A ) \), gdzie \( A \) jest zbiorem wszystkich możliwych kolorowań zbioru \( X \). Podstawiając, w Twierdzeniu 5.4, za funkcję \( f \) wskaźnik kolorowania \( {\sf ind} \) otrzymujemy

\( \displaystyle \sum_{\omega\in D}{\sf ind}( \omega ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} ( \sum_{\omega \in {\sf Fix}( \widehat{g} )} {\sf ind}( \omega ) ). \)

Korzystając z definicji wskaźnika kolorowania dostajemy

\( \displaystyle {\sf U}_{D}( x_1,x_2,\ldots,x_k ) =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ). \)

Zbiór \( {\sf Fix}( \widehat{g} ) \) jest zbiorem kolorowań, przy których elementy z tego samego cyklu otrzymują tę samą barwę. A zatem, z Twierdzenia 5.8 wynika, że

\( \displaystyle {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) =\prod_{i=1}^l( x_1^{m_i} +x_2^{m_i} +\ldots+ x_k^{m_i} )=\prod_{i=1}^l\sigma_{m_i}, \)

gdzie \( m_i \) jest rozmiarem \( i \)-tego cyklu. Niech \( \alpha_i \) będzie liczbą cykli w \( g \) o długości \( i \). Otrzymujemy więc

\( \begin{align*} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) & =\sigma_1^{\alpha_1}\cdot\sigma_2^{\alpha_2}\cdot\ldots\cdot\sigma_n^{\alpha_n} \\ & =\zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)

Obserwacja 5.6 daje więc teraz

\( \begin{align*} {\sf U}_{D}( x_1,x_2,\ldots,x_k ) & =\frac{1}{\vert \widehat{G} \vert}\sum_{\widehat{g}\in \widehat{G}} {\sf U}_{{\sf Fix}( \widehat{g} )}( x_1,x_2,\ldots,x_k ) \\ & =\frac{1}{\vert G \vert}\sum_{g\in G} \zeta_{g}( \sigma_1,\sigma_2,\ldots,\sigma_n ) \\ & =\zeta_{G}( \sigma_1,\sigma_2,\ldots,\sigma_n ). \end{align*} \)

Przykład

Użyjemy opisanych twierdzeń do wyznaczenia liczby wszystkich nieizomorficznych pokolorowań wierzchołków kwadratu na dwa kolory. Rozważmy więc wszystkie osiem symetrii kwadratu, jak przedstawiono na animacji.

Grupa permutacji \( G_{\diamondsuit} \) wyznaczona przez te symetrie ma \( 8 \) następujących elementów:

\( \begin{array} {lp{20mm}l} id\ =\ ( 0 )\!( 1 )\!( 2 )\!( 3 ) & & g_4\ =\ ( 0 )\!( 3 )\!( 12 ) \\ g_1\ =\ ( 0123 ) & & g_5\ =\ ( 1 )\!( 2 )\!( 03 ) \\ g_2\ =\ ( 02 )\!( 13 ) & & g_6\ =\ ( 02 )\!( 13 ) \\ g_3\ =\ ( 0321 ) & & g_7\ =\ ( 01 )\!( 23 ) \end{array} \)

Z podanego rozkładu na cykle dostajemy, że indeks grupy \( G_{\diamondsuit} \) to

\( \zeta_{G_{\diamondsuit}}( x_1,x_2,x_3,x_4 ) =\frac{1}{8}( x_1^4+2x_1^2x_2+3x_2^2+2x_4 ). \)

Aby znaleźć liczbę nieizomorficznych kolorowań takich, że \( i \) wierzchołków jest pokolorowanych na biało \( □ \), a pozostałe \( 4-i \) na czarno \( ■ \), wystarczy wyliczyć współczynnik przy \( □^i ■^{4-i} \) w funkcji tworzącej postaci

\( \begin{align*} {\sf U}_{D}( □,■ ) & =\zeta_{G_{\diamondsuit}}( □+■,\ □^2+■^2,\ □^3+■^3,\ □^4+■^4 ) \\ & =□^4+□^3■+2□
^2■^2+□ ■^3+■^4. \end{align*} \)

Rysunek przedstawia wszystkie możliwe nieizomorficzne kolorowania.

Nieizomorficzne kolorowania wierzchołków kwadratu

Ciała skończone

Wstęp

---

Ciała odgrywają olbrzymią rolę we wszystkich prawie dziedzinach matematyki. Chyba najbardziej znanym ciałem jest zbiór liczb rzeczywistych z dodawaniem i mnożenie. Wraz z ciałem liczb zespolonych, ciało liczb rzeczywistych stanowi podstawę Analizy Matematycznej. Ten wykład poświęcony jest podstawowym własnościom ciał skończonych.

Koncepcje ciała stosowali jako pierwsi Niels Abel i Evariste Galois w swoich pracach dotyczących rozwiązywalności równań algebraicznych. W 1893, Heinrich Weber podał pierwszą kompletną definicję abstrakcyjnego ciała. W 1910, Ernst Steinitz opublikował pracę, która dała podstawy współczesnej teorii ciał.

Zastosowanie teorii liczb w kryptografii

Wstęp

---

Kryptografia jest dziedziną informatyki, zajmującą się zagadnieniami bezpieczeństwa informacji. W szczególności kryptografia traktuje o: kodowaniu/dekodowaniu, autoryzacji, kontroli dostępu. W drugiej połowie XX wieku kryptografia całkowicie zmieniła swoje oblicze, głównie dzięki stworzeniu kryptosystemów o publicznym kluczu. Obecnie jest to dziedzina, w której znajduje zastosowanie wiele rozważań z teorii informacji, złożoności obliczeniowej, statystyki, kombinatoryki i, na co zwracamy uwagę, z teorii liczb.

W tym wykładzie przedstawiamy, bardzo pobieżnie, model matematyczny kodowania/dekodowania wiadomości. Później opisujemy dwa kryptosystemy: Cezara (bardziej jako przykład dydaktyczny) oraz RSA. W drugiej części wykładu poznamy algorytmy sprawdzające czy liczba jest pierwsza.

Metoda przybliżeń

Metoda przybliżeń

---

W pewnych sytuacjach łatwiejsze do uzyskania, ale słabsze oszacowanie zastosowane w odpowiedni sposób może prowadzić do lepszego końcowego szacowania zachowania asymptotycznego. Poznamy tę metodę w kilku kolejnych przykładach.

Przykład

Dla ciągu zadanego przez

\( \displaystyle \begin{align*} a_0 & =1, \\ a_{n+1} & =\frac{1}{n^3}\sum_{i=0}^{n-1}a_i, \end{align*} \)

najpierw dowodzimy indukcyjnie, że \( \displaystyle 0 < a_n\leq 1 \), czyli \( \displaystyle a_n=O(1) \). Podstawiając uzyskane oszacowanie do równania rekurencyjnego otrzymujemy:

\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^{n}a_i=\frac{1}{n^3}\cdot \sum_{i=0}^n O(1)=\frac{1}{n^3}\cdot O( \sum_{i=0}^n1 )=\frac{1}{n^3}\cdot O(n)=O( \frac{1}{n^2} ). \)

Operację tę możemy powtórzyć uzyskując jeszcze lepsze oszacowanie

\( \displaystyle \begin{align*} a_n & =\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}( a_0+\sum_{i=1}^na_i )=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^{n}O( \frac{1}{n^2} )= \frac{1}{n^3}+\frac{1}{n^3}O(1) \\ & =O( \frac{1}{n^3} ). \end{align*} \)

Wykorzystaliśmy tu fakt, iż szereg \( \displaystyle \sum_{i=0}^{\infty}\frac{1}{i^2} \) jest zbieżny. Zauważmy też, że następne powtórzenie podobnej procedury szacującej już nam nic nie da.

\( \displaystyle a_n=\frac{1}{n^3}\sum_{i=0}^na_i=\frac{1}{n^3}+\frac{1}{n^3}\sum_{i=1}^nO( \frac{1}{n^3} )=\frac{1}{n^3}+\frac{1}{n^3}\cdot O( \frac{1}{n^2} )=O( \frac{1}{n^3} ). \)

Przykład

Niech ciąg \( \displaystyle b_n \) spełnia

\( \displaystyle b_n\cdot\ln{b_n}=n. \)

Z monotoniczności funkcji \( \displaystyle n\ln{n} \) dostajemy, że \( \displaystyle 0 < b_n < n \). Podstawiając to oszacowanie za drugie wystąpienie \( \displaystyle b_n \) w równaniu otrzymujemy:

\( \displaystyle n=b_n\cdot\ln{b_n} < b_n\ln{n}, \)

czyli \( \displaystyle b_n>\frac{n}{\ln{n}} \). Podstawiając powtórnie dostajemy:

\( \displaystyle n=b_n\ln{b_n}>b_n\cdot\ln{\frac{n}{\ln{n}}}, \)

czyli \( \displaystyle b_n < \frac{n}{\ln{n}-\ln{\ln{n}}} \). Uzyskaliśmy zatem, że \( \displaystyle b_n=\Theta( \frac{n}{\ln{n}} ) \).

Na zakończenie tego wykładu poznamy jeszcze jeden symbol asymptotyczny. Jest on podobny do \( \displaystyle \Theta \) lecz znacznie precyzyjniejszy.

Funkcje asymptotycznie równe to takie funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \), że

\( \displaystyle \lim_{narrow\infty}\frac{f(n)}{g(n)}=1. \)
Fakt, że funkcje \( \displaystyle f(n) \) i \( \displaystyle g(n) \) są asymptotycznie równe zapisujemy jako \( \displaystyle f(n)\sim g(n) \).

Jednym z najbardziej znanych przybliżeń asymptotycznych jest tzw. Wzór Stirlinga przybliżający zachowanie silni.

Twierdzenie 9.5 [wzór Stirlinga]

\( \displaystyle n!\sim \sqrt{2\pi n}( \frac{n}{e} )^n. \)
Wzór ten został odkryty przez Abrahama de Moivre w postaci

\( \displaystyle n!\sim c \cdot n^{n+1/2} e^{-n}, \)
dla pewnej stałej \( \displaystyle c \). Wkładem Jamesa Stirlinga było pokazanie, że stałą tą jest \( \displaystyle c=\sqrt{2\pi} \). Dowód tego oszacowania wykracza poza metody tego kursu. W oszacowaniach przez nierówności przydatna jest następująca wersja wzoru Stirlinga:

\( \displaystyle \sqrt{2\pi n}( \frac{n}{e} )^ne^{-(12n+1)}\leq n!\leq \sqrt{2\pi n}( \frac{n}{e} )^{n}e^{-12n} \)
Innym ważnym przybliżeniem asymptotycznym jest wzór na liczbę podziałów liczby naturalnej \( \displaystyle n \) na sumy dodatnich liczb naturalnych, tzn. asymptotyczne przybliżenie funkcji \( \displaystyle p_n = \sum_{k=1}^n P(n,k) \) .

Twierdzenie 9.6

\( \displaystyle p_n \sim \frac{e^{\pi\sqrt{\frac{2n}{3}}}}{4n\sqrt{3}} \)

Podamy też asymptotyczne przybliżenie na liczbę liczb pierwszych nie większych niż \( \displaystyle n \).

Twierdzenie 9.7

Jeśli \( \displaystyle \pi(n) \) oznacza liczbę liczb pierwszych w zbiorze \( \displaystyle \lbrace 1,2,3,\ldots,n \rbrace \), to

\( \displaystyle \pi(n) \sim \frac{n}{\ln n} \)