Matematyka dyskretna 2/Wykład 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
jest spójny, potrzeba by miał on więcej niż 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
, jeśli oraz , to dla któregoś mamy .Dowód
Wykorzystując założenia twierdzenia otrzymujemy następujące oszacowanie:
Tak więc
Ponieważ moce zbiorów są liczbami całkowitymi otrzymujemy, że ta maksymalna
musi wynosić co najmniej .

Uogólniona Zasada Szufladkowa wymusza, że któryś składnik podziału musi mieć co najmniej Twierdzenie 3.1.
elementów. Zasadę tę można uogólnić w ten sposób, by zadając najpierw ciąg liczb naturalnych , w miejsce jednej liczby , i podział żądać by któryś składnik był co najmniej elementowy. Otrzymujemy w ten sposób Zasadę Podziałową. Przy wszystkich jest toTwierdzenie 3.2 [Zasada podziałowa]
Niech
będzie ciągiem liczb naturalnych. Jeśli
to dla pewnego .
Dowód
Załóżmy, wbrew tezie twierdzenia, że jakiś
o mocy rozkłada się na sumę , przy czym każdy składnik ma moc . Wtedy nierówność dwu skrajnych liczb w
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
, jeżeli tylko graf prosty posiada co najmniej elementów, to zawiera jako podgraf indukowany klikę lub antyklikę .Dowód
Niech
. Dla każdego definiujemy dwa zbiory: odpowiednio zbiór sąsiadów wierzchołka oraz zbiór elementów nie będących sąsiadami :
Zdefiniujemy ciąg grafów .
Niech .
Wybierzmy jakiś element
i zdefiniujmy podgraf grafu
w następujący sposób
Zauważmy, że .
Następnie wybieramy dowolny element
i analogicznie definiujemy .
W ogólności dla graf definiujemy poprzez
gdzie jest dowolnie wybranym elementem ze zbioru .
Każdy kolejny graf zmniejszy się o co najwyżej połowę elementów,
tak więc cały czas zachowana jest własność
To z kolei implikuje, że dla zbiór jest niepusty,
co pozwala zawsze na wybór kolejnych wierzchołków
potrzebnych do zdefiniowania kolejnych grafów .
Każdy element albo sąsiaduje ze wszystkimi wierzchołkami grafu
albo też nie jest połączony krawędzią z żadnym z wierzchołków w .
Tak więc w ciągu
można wyróżnić podciąg
elementów pierwszego typu oraz podciąg
elementów drugiego typu.
Element sąsiaduje z każdym elementem z ,
a więc także z każdym dla .
Z kolei sąsiaduje z każdym elementem z ,
a więc także z każdym dla i tak dalej.
Zatem zbiór wierzchołków w grafie
indukuje -elementową klikę.
Analogicznie
jest -elementową antykliką.
Oczywiście .
Tak więc na mocy Uogólnionej Zasady Szufladkowej Dirichlet'a otrzymujemy,
że albo , 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 będzie rodziną -elementowych podzbiorów zbioru . Tak więc pokrycie to nic innego jak pokrycie rodziny , gdzie . Oznacza to, że w Zasadzie Podziałowej żądamy podzbioru , dla którego istnieje , takie że oraz że dowolny singleton zawarty w należy do .
Z drugiej strony graf prosty z Twierdzenia 3.3 to para , gdzie . Daje to więc podział . Żądanie -elementowej kliki jest żądaniem -elementowego podzbioru zbioru takiego, że dowolna "krawędź" pomiędzy elementami w , czyli dowolny element , jest . Analogicznie poszukiwana antyklika jest po prostu podzbiorem zbioru takim, ż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 . Nie podamy też w tym wykładzie jego dowodu.
Twierdzenie 3.4 [F. P. Ramsey 1930]
Dla dowolnych
oraz dla dowolnego ciągu liczb naturalnych istnieje liczba o następującej własności:- Dla każdego zbioru o co najmniej elementach i dowolnego rozbicia
, istnieje podzbiór zbioru o co najmniej elementach taki, że przy pewnym .
Liczba Ramseya
Szczególnym przypadkiem jest .
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
. Jak widać nawet dla małych wartości oraz , dokładne wartości liczb nie są znane.
Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a
przedstawimy kilka twierdzeń przybliżających te liczby.
Wartość liczby Ramsey'a z indeksem Twierdzenie 3.2). Zasadę tę można przeformułować jako:
jest opisana w Zasadzie Podziałowej (
Dla liczb Ramsey'a z indeksem
podamy, bez dowodu, następujące oszacowanie górne.Twierdzenie 3.5
Z uwagi na Twierdzenie 3.3, ważną rolę odgrywają liczby Ramsey'a postaci a w szczególności . O nich możemy powiedzieć już trochę więcej w tym wykładzie.
Twierdzenie 3.6
Dla dowolnych
oraz mamy:
Dowód
Niech
będzie zbiorem o elementach, i . Wtedy każdy podział indukuje podział , gdzie
Ponieważ moc
realizuje liczbę Ramsey'a ,
to w zbiorze
- istnieje podzbiór o mocy , w którym dowolny podzbiór -elementowy należy do ,
lub też
- istnieje podzbiór o mocy , w którym dowolny podzbiór -elementowy należy do .
Bez straty ogólności załóżmy, że zachodzi przypadek pierwszy. Z definicji liczb Ramsey'a oraz z faktu, że
otrzymujemy następujące dwa przypadki, których analiza jest podobna:- W istnieje podzbiór , o mocy , i którego każdy -elementowy podzbiór należy do .
- W istnieje podzbiór , o mocy , i którego każdy -elementowy podzbiór należy do .
Z uwagi na symetrię przeanalizujemy jedynie pierwszy przypadek. Niech
ma -elementów. Jeśli , to zawiera się w , i co za tym idzie, należy do . Jeśli zaś , to jest -elementowym podzbiorem zbioru . A więc należy do . Z definicji rodziny otrzymujemy, że i w tym przypadku należy do .W konsekwencji otrzymujemy, że w
istnieje podzbiór (w rozpatrzonym przypadku jest to ), którego każdy -elementowy podzbiór należy do , lub też w istnieje podzbiór (w rozpatrzonym przypadku jest to ), którego każdy -elementowy podzbiór należy do . Ponieważ zbiór ma moc , to
Twierdzenie 3.7
Dla dowolnych
Dowód
Dowód przeprowadzimy indukcyjnie ze względu na
oraz . Dla zachodzi równość
a dla zachodzi równość
Przejdźmy więc do przypadku, gdy .
Na mocy założenia indukcyjnego mamy:
Dla Twierdzenie 3.6 mówi, że
Tak więc
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
Innymi słowy, rodzina jest dwukolorowalna,
jeśli istnieje podzbiór taki, że
Twierdzenie 3.8
Niech
oraz . Jeśli , to rodzina jest dwukolorowalna.Dowód
Niech
. Policzmy pary w zbiorze
Liczba podzbiorów zbioru zawierających
jest równa liczbie podzbiorów zbioru rozłącznych z ,
i ponieważ , to wynosi ona . Zatem
Niech teraz rodzina nie będzie dwukolorowalna,
czyli dla każdego zbioru istnieje taki,
że albo .
Tak więc par w jest co najmniej tyle co podzbiorów ,
a więc
skąd natychmiast

Twierdzenie 3.9 [P. Erd{o}s 1947]
Dowód
Niech
będzie zbiorem o elementach. Połóżmy
i dalej
Wtedy .
Ponieważ ma elementów,
to rodzina nie jest dwukolorowalna,
tak więc na mocy Twierdzenia 3.8 trzymujemy:
Z kolei definicja rodziny daje ,
a więc
Otrzymujemy więc, że
co z kolei implikuje, że
Oszacowanie Sterlinga na daje
i w konsekwencji otrzymujemy:

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
oraz istnieje graf prosty taki, że jakkolwiek nie podzielimy zbioru krawędzi na zbiory , to będzie podgrafem indukowanym grafu lub będzie podgrafem indukowanym grafu .