Matematyka dyskretna 2/Wykład 3: Własności podziałowe i Twierdzenie Ramsey'a

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 .

End of proof.gif

Uogólniona Zasada Szufladkowa wymusza, że któryś składnik podziału musi mieć co najmniej 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 to Twierdzenie 3.1.

Twierdzenie 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.

End of proof.gif

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.

End of proof.gif

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 to najmniejsza taka liczba , dla której spełniony jest warunek .
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.

Uwaga

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



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

End of proof.gif

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.

End of proof.gif

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

Dwukolorowalna rodzina -elementowych podzbiorów zbioru to rodzina , dla której istnieje takie kolorowanie elementów zbioru dwoma kolorami tak, by żaden zbiór nie składał się z elementów tego samego koloru.
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



End of proof.gif

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:



End of proof.gif

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 .