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

From Studia Informatyczne

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}=\left( V,E \right) jest spójny, potrzeba by miał on więcej niż \left\vert V \right\vert\cdot(\left\vert V \right\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 \left\vert X \right\vert\geq (q-1)t+1, to dla któregoś i mamy \left\vert X_i \right\vert\geq q.

Dowód

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


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


Tak więc


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


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

image:End_of_proof.gif

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\left\vert X \right\vert>\left( \sum_{i=1}^t{q_i} \right)-t,


to \left\vert X_i \right\vert\geq q_i dla pewnego i.

Dowód

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


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


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

image: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 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:=\left\vert \mathbf{G} \right\vert\geq 2^{2r-1}. Dla każdego x\in{\sf V}\!\left(\mathbf{G}\right) definiujemy dwa zbiory: odpowiednio zbiór sąsiadów wierzchołka x oraz zbiór elementów nie będących sąsiadami x:


\aligned {\sf N}_{\mathbf{G}}\!\left( x \right)&=\left\lbrace y\in{\sf V}\!\left(\mathbf{G}\right):\ xy\in{\sf E}\!\left(\mathbf{G}\right) \right\rbrace,\\ {\sf A}_{\mathbf{G}}\!\left( x \right)&=\left\lbrace y\in{\sf V}\!\left(\mathbf{G}\right):\ xy\notin{\sf E}\!\left(\mathbf{G}\right) \right\rbrace. \endaligned


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}\!\left(\mathbf{G}\right) 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}}\!\left( x_1 \right)}, & \textrm{jeżeli}\ \left\vert {\sf A}_{\mathbf{G}_0}\!\left( x_1 \right) \right\vert\leq\left\vert {\sf N}_{\mathbf{G}_0}\!\left( x_1 \right) \right\vert,\\ {\mathbf{G}_0}|_{{\sf A}_{\mathbf{G}_0}\!\left( x_1 \right)}, & \textrm{w przeciwnym wypadku.} \end{array}   \right.


Zauważmy, że \left\vert {\sf V}\!\left(\mathbf{G}_1\right) \right\vert\geq2^{2r-2}. Następnie wybieramy dowolny element x_2\in{\sf V}\!\left(\mathbf{G}_1\right) 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}}\!\left( x_i \right)}, & \textrm{jeżeli}\ \left\vert {\sf A}_{\mathbf{G}_{i-1}}\!\left( x_i \right) \right\vert\leq\left\vert {\sf N}_{\mathbf{G}_{i-1}}\!\left( x_i \right) \right\vert,\\ {\mathbf{G}_{i-1}}|_{{\sf A}_{\mathbf{G}_{i-1}}\!\left( x_i \right)}, & \textrm{w przeciwnym wypadku,} \end{array}   \right.


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


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


To z kolei implikuje, że dla i\leq 2r-1 zbiór {\sf V}\!\left(\mathbf{G}_i\right) 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}\!\left(\mathbf{G}_{j_1}\right), 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}\!\left(\mathbf{G}_{j_2}\right), a więc także z każdym x_{j_i} dla i\geq 3 i tak dalej. Zatem zbiór wierzchołków \left\lbrace x_{j_1},\ldots,x_{j_s} \right\rbrace w grafie \mathbf{G} indukuje s-elementową klikę. Analogicznie \mathbf{G}|_{\left\lbrace x_{l_1},\ldots,x_{l_t} \right\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.

image: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 \mathscr{P}_{r}\!\left( X \right) 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}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_k, gdzie \mathscr{A}_i=\left\lbrace \left\lbrace x \right\rbrace:\ x\in X_i \right\rbrace. Oznacza to, że w Zasadzie Podziałowej żądamy podzbioru Y\subseteq X, dla którego istnieje i, takie że \left\vert Y \right\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}=\left( V,E \right), gdzie E\subseteq\mathscr{P}_{2}\!\left( V \right). Daje to więc podział \mathscr{P}_{2}\!\left( V \right)=E\cup\left( \mathscr{P}_{2}\!\left( V \right)- E \right). Żą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}\!\left( K \right), jest E. Analogicznie poszukiwana antyklika jest po prostu podzbiorem A zbioru V takim, że \mathscr{P}_{2}\!\left( A \right)\subseteq \mathscr{P}_{2}\!\left( V \right)- 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}\!\left( X \right)=\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}\!\left( Y \right)\subseteq \mathscr{A}_i przy pewnym i=1,\ldots,t.

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

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}\!\left( m,n \right). Jak widać nawet dla małych wartości n oraz m, dokładne wartości liczb {\sf R}_{2}\!\left( m,n \right) nie są znane.


\array {|c||c|c|c|c|c|c|c|c|} \hline n\downarrow\ m\rightarrow &  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 \endarray


Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a {\sf R}\!\left( q_1,\ldots,q_t \right) 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}\!\left( q_1,\ldots,q_t \right)=\left( \sum_{i=1}^t{q_i} \right)-t+1.


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

Twierdzenie 3.5


{\sf R}\!\left( q_1,\ldots,q_t \right)\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}\!\left( m,n \right) a w szczególności {\sf R}\!\left( m,n \right)={\sf R}_{2}\!\left( m,n \right). 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}\!\left( m,n \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( m-1,n \right),{\sf R}_{r}\!\left( m,n-1 \right) \right)+1.

Dowód

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


\aligned \mathscr{A}'_1 &= \left\lbrace  A-\left\lbrace x_0 \right\rbrace :\ A\in\mathscr{A}_1\ \&\ x_0\in A  \right\rbrace,\\ \mathscr{A}'_2 &= \left\lbrace  A-\left\lbrace x_0 \right\rbrace :\ A\in\mathscr{A}_2\ \&\ x_0\in A  \right\rbrace. \endaligned


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

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

lub też

  • istnieje podzbiór X_2\subseteq X-\left\lbrace x_0 \right\rbrace o mocy \left\vert X_2 \right\vert={\sf R}_{r}\!\left( m,n-1 \right), 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 \left\vert X_1 \right\vert={\sf R}_{r}\!\left( m-1,n \right) otrzymujemy następujące dwa przypadki, których analiza jest podobna:

  • W X_1 istnieje podzbiór X_{11}\subseteq X_1, o mocy \left\vert X_{11} \right\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 \left\vert X_{12} \right\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\left\lbrace x_0 \right\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-\left\lbrace x_0 \right\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\left\lbrace x_0 \right\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}}\!\left( {\sf R}_{r}\!\left( m-1,n \right),{\sf R}_{r}\!\left( m,n-1 \right) \right)+1, to

{\sf R}_{r}\!\left( m,n \right)\leq {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( m-1,n \right),{\sf R}_{r}\!\left( m,n-1 \right) \right)+1.
image:End_of_proof.gif

Twierdzenie 3.7

Dla dowolnych m, n \geq 2


{\sf R}\!\left( m,n \right)\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}\!\left( m,2 \right)=m={{m}\choose{1}}={{m+n-2}\choose{m- 1}},


a dla m=2 zachodzi równość


{\sf R}\!\left( 2,n \right)=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}\!\left( m-1,n \right)\leq{{m+n-3}\choose{m-2}},\quad{\sf R}\!\left( m,n-1 \right)\leq{{m+n-3}\choose{m-1}}.


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


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


Tak więc


\aligned {\sf R}\!\left( m,n \right) &\leq{\sf R}\!\left( m-1,n \right) + {\sf R}\!\left( m,n-1 \right)\\ &\leq{{m+n-3}\choose{m-2}}+{{m+n-3}\choose{m-1}}\\ &={{m+n-2}\choose{m-1}}, \endaligned


co kończy dowód.

image: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 n-elementowych podzbiorów zbioru X to rodzina \mathscr{X}\subseteq\mathscr{P}_{n}\!\left( X \right), 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}\!\left( X \right). Jeśli \left\vert X \right\vert < 2^{n-1}, to rodzina \mathscr{X} jest dwukolorowalna.

Dowód

Niech m:=\left\vert X \right\vert. Policzmy pary w zbiorze


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


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


\left\vert \mathscr{A} \right\vert=\left\vert \mathscr{X} \right\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\left\vert \mathscr{A} \right\vert=\left\vert \mathscr{X} \right\vert\cdot 2^{m-n+1},


skąd natychmiast


\left\vert \mathscr{X} \right\vert\geq 2^{n-1}.


image:End_of_proof.gif

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

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


Dowód

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


X=\mathscr{P}_{2}\!\left( Y \right)


i dalej


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


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


\left\vert \mathscr{X} \right\vert\geq 2^{{n\choose 2}-1}


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


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


Otrzymujemy więc, że


m^n\geq n!\cdot2^{\left( n^2-n-2 \right)/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}\left( \frac{1}{\sqrt{2}}-o\left( 1 \right) \right).


Oszacowanie Sterlinga na n! daje


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


i w konsekwencji otrzymujemy:


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


image: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 \mathbf{H}_1 oraz \mathbf{H}_2 istnieje graf prosty \mathbf{G} taki, że jakkolwiek nie podzielimy zbioru krawędzi {\sf E}\!\left(\mathbf{G}\right) na zbiory E_1,E_2, to \mathbf{H}_1 będzie podgrafem indukowanym grafu \left( {\sf V}\!\left(\mathbf{G}\right),E_1 \right) lub \mathbf{H}_2 będzie podgrafem indukowanym grafu \left( {\sf V}\!\left(\mathbf{G}\right),E_2 \right).