Tekst źródłowy strony 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 <math>\mathbf{G}=\left( V,E \right)</math> jest spójny, 
potrzeba by miał on więcej niż <math>\left\vert V \right\vert\cdot(\left\vert V \right\vert-1)/2</math> 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]|tw 3.1|
Dla dowolnej liczby <math>q\in\mathbb{N}</math>, 
jeśli <math>X=X_1\cup\ldots\cup X_t</math> oraz <math>\left\vert X \right\vert\geq (q-1)t+1</math>, 
to dla któregoś <math>i</math> mamy <math>\left\vert X_i \right\vert\geq q</math>.
}}

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


<center><math>(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}</math></center>


Tak więc


<center><math>(q-1)+\frac{1}{t}=\frac{(q-1)t+1}{t}\leq\max_{i=1,\ldots, t}{\left\vert X_i \right\vert}</math></center>


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

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

{{twierdzenie|3.2 [Zasada podziałowa]|tw 3.2|
Niech <math>q_1,\ldots,q_k</math> będzie ciągiem liczb naturalnych. Jeśli


<center><math>X=X_1\cup\ldots\cup X_t\quad\text{oraz}\quad\left\vert X \right\vert>\left( \sum_{i=1}^t{q_i} \right)-t</math>,</center>


to <math>\left\vert X_i \right\vert\geq q_i</math> dla pewnego <math>i</math>.
}}

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


<center><math>\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)</math>,</center>


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]|tw 3.3|
Dla dowolnej liczby <math>r\in\mathbb{N}</math>, 
jeżeli tylko graf prosty <math>\mathbf{G}</math> posiada co najmniej <math>2^{2r-1}</math> elementów, 
to <math>\mathbf{G}</math> zawiera jako podgraf indukowany klikę <math>\mathcal{K}_{r}</math> 
lub antyklikę <math>\mathcal{A}_{r}</math>.
}}

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


<center><math>\begin{align} \mathsf{ N}_{\mathbf{G}}\!\left( x \right)&=\left\lbrace y\in\mathsf{ V}\!\left(\mathbf{G}\right):\ xy\in\mathsf{ E}\!\left(\mathbf{G}\right) \right\rbrace,\\
\mathsf{ A}_{\mathbf{G}}\!\left( x \right)&=\left\lbrace y\in\mathsf{ V}\!\left(\mathbf{G}\right):\ xy\notin\mathsf{ E}\!\left(\mathbf{G}\right) \right\rbrace.
\end{align}</math></center>


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


<center><math>\mathbf{G}_1 = 
\begin{cases}
{\mathbf{G}_0}|_{\mathsf{ N}_{{\mathbf{G}_0}}\!\left( x_1 \right)}, & \text{jeżeli} \left\vert \mathsf{ A}_{\mathbf{G}_0}\!\left( x_1 \right) \right\vert\leq\left\vert \mathsf{ N}_{\mathbf{G}_0}\!\left( x_1 \right) \right\vert,\\
{\mathbf{G}_0}|_{\mathsf{ A}_{\mathbf{G}_0}\!\left( x_1 \right)}, & \text{w przeciwnym wypadku.}
\end{cases}  
</math></center>


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


<center><math>\mathbf{G}_i = 
\begin{cases}
{\mathbf{G}_{i-1}}|_{\mathsf{ N}_{\mathbf{G}_{i-1}}\!\left( x_i \right)}, & \text{jeżeli} \left\vert \mathsf{ A}_{\mathbf{G}_{i-1}}\!\left( x_i \right) \right\vert\leq\left\vert \mathsf{ N}_{\mathbf{G}_{i-1}}\!\left( x_i \right) \right\vert,\\
{\mathbf{G}_{i-1}}|_{\mathsf{ A}_{\mathbf{G}_{i-1}}\!\left( x_i \right)}, & \text{w przeciwnym wypadku,}
\end{cases}  
</math></center>


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


<center><math>\left\vert \mathsf{ V}\!\left(\mathbf{G}_i\right) \right\vert\geq2^{2r-(i+1)}. 
</math></center>


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

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

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

Następne twierdzenie jest uogólnieniem [[#tw_3.1|Twierdzeń 3.1]], [[#tw_3.2|3.2]], oraz [[#tw_3.3|3.3]]. 
Warto zauważyć, że poniższe twierdzenie Ramsey'a nie podaje niestety 
minimalnego oszacowania na moc zbioru <math>X</math>. 
Nie podamy też w tym wykładzie jego dowodu.

{{twierdzenie|3.4 [F. P. Ramsey 1930]|tw 3.4|
Dla dowolnych <math>r,t\in\mathbb{N}</math> 
oraz dla dowolnego ciągu liczb naturalnych <math>q_1,\ldots, q_t</math> 
istnieje liczba <math>n</math> o następującej własności:

; <math>(*)</math> Dla każdego zbioru <math>X</math> o co najmniej <math>n</math> elementach i dowolnego rozbicia 
<math>\mathcal{P}_{r}\!\left( X \right)=\mathcal{A}_1\cup\ldots\cup\mathcal{A}_t</math>, istnieje podzbiór <math>Y</math> zbioru <math>X</math> o co najmniej <math>q_i</math> elementach taki, że <math>\mathcal{P}_{r}\!\left( Y \right)\subseteq \mathcal{A}_i</math> przy pewnym <math>i=1,\ldots,t</math>.

}}

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

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


<center><math>
\begin{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
\end{array}
</math></center>


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

{{uwaga|||
Wartość liczby Ramsey'a z indeksem <math>r=1</math> 
jest opisana w Zasadzie Podziałowej ([[#tw_3.2|Twierdzenie 3.2]]). 
Zasadę tę można przeformułować jako:


<center><math>\mathsf{ R}_{1}\!\left( q_1,\ldots,q_t \right)=\left( \sum_{i=1}^t{q_i} \right)-t+1</math></center>


}}

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

{{twierdzenie|3.5|tw 3.6|


<center><math>\mathsf{ R}\!\left( q_1,\ldots,q_t \right)\leq\frac{t^{q_1+\ldots+q_t-2t+1}-1}{t-1}+1</math></center>


}}

Z uwagi na [[#tw_3.3|Twierdzenie 3.3]], 
ważną rolę odgrywają liczby Ramsey'a postaci <math>\mathsf{ R}_{r}\!\left( m,n \right)</math>
a w szczególności <math>\mathsf{ R}\!\left( m,n \right)=\mathsf{ R}_{2}\!\left( m,n \right)</math>. 
O nich możemy powiedzieć już trochę więcej w tym wykładzie.

{{twierdzenie|3.6|tw 3.6|
Dla dowolnych <math>m, n \geq 2</math> oraz <math>r \geq 1</math> mamy:


<center><math>\mathsf{ R}_{r}\!\left( m,n \right)\leq \mathsf{ R}_{{r-1}}\!\left( \mathsf{ R}_{r}\!\left( m-1,n \right),\mathsf{ R}_{r}\!\left( m,n-1 \right) \right)+1</math></center>

}}

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


<center><math>\begin{align} \mathcal{A}'_1 &= \left\lbrace  A-\left\lbrace x_0 \right\rbrace :\ A\in\mathcal{A}_1\ \&\ x_0\in A  \right\rbrace,\\
\mathcal{A}'_2 &= \left\lbrace  A-\left\lbrace x_0 \right\rbrace :\ A\in\mathcal{A}_2\ \&\ x_0\in A  \right\rbrace.
\end{align}</math></center>


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

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

lub też

* istnieje podzbiór <math>X_2\subseteq X-\left\lbrace x_0 \right\rbrace</math> o mocy <math>\left\vert X_2 \right\vert=\mathsf{ R}_{r}\!\left( m,n-1 \right)</math>, w którym dowolny podzbiór <math>(r-1)</math>-elementowy należy do <math>\mathcal{A}'_2</math>.

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

* W <math>X_1</math> istnieje podzbiór <math>X_{11}\subseteq X_1</math>, o mocy <math>\left\vert X_{11} \right\vert=m-1</math>, i którego każdy <math>r</math>-elementowy podzbiór należy do <math>\mathcal{A}_1</math>.

* W <math>X_1</math> istnieje podzbiór <math>X_{12}\subseteq X_1</math>, o mocy <math>\left\vert X_{12} \right\vert=n</math>, i którego każdy <math>r</math>-elementowy podzbiór należy do <math>\mathcal{A}_2</math>.

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

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

<center><math>\mathsf{ R}_{r}\!\left( m,n \right)\leq \mathsf{ R}_{{r-1}}\!\left( \mathsf{ R}_{r}\!\left( m-1,n \right),\mathsf{ R}_{r}\!\left( m,n-1 \right) \right)+1</math></center>

}}

{{twierdzenie|3.7|tw 3.7|
Dla dowolnych <math>m, n \geq 2</math>


<center><math>\mathsf{ R}\!\left( m,n \right)\leq {{m+n-2}\choose{m-1}}</math></center>


}}

{{dowod|||
Dowód przeprowadzimy indukcyjnie ze względu na <math>n</math> oraz <math>m</math>. 
Dla <math>n=2</math> zachodzi równość


<center><math>\mathsf{ R}\!\left( m,2 \right)=m={{m}\choose{1}}={{m+n-2}\choose{m-
1}}</math>,</center>


a dla <math>m=2</math> zachodzi równość


<center><math>\mathsf{ R}\!\left( 2,n \right)=n={{n}\choose{1}}={{m+n-2}\choose{m-1}}</math></center>


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


<center><math>\mathsf{ R}\!\left( m-1,n \right)\leq{{m+n-3}\choose{m-2}},\quad\mathsf{ R}\!\left( m,n-1 \right)\leq{{m+n-3}\choose{m-1}}</math></center>


Dla <math>r=2</math> [[#tw_3.6|Twierdzenie 3.6]]  mówi, że


<center><math>\mathsf{ R}_{2}\!\left( m,n \right)\leq\mathsf{ R}_{1}\!\left( \mathsf{ R}_{2}\!\left( m-1,n \right),\mathsf{ R}_{2}\!\left( m,n-1 \right) \right)+1 = \mathsf{ R}_{2}\!\left( m-1,n \right) + \mathsf{ R}_{2}\!\left( m,n-1 \right)</math></center>


Tak więc


<center><math>\begin{align} \mathsf{ R}\!\left( m,n \right)
&\leq\mathsf{ R}\!\left( m-1,n \right) + \mathsf{ 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}},
\end{align}</math></center>


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''' <math>n</math>-elementowych podzbiorów zbioru <math>X</math> 
to rodzina <math>\mathcal{X}\subseteq\mathcal{P}_{n}\!\left( X \right)</math>, 
dla której istnieje takie kolorowanie elementów zbioru <math>X</math> dwoma kolorami tak, 
by żaden zbiór <math>A\in\mathcal{X}</math> nie składał się z elementów tego samego  koloru.<br>
Innymi słowy, rodzina <math>\mathcal{X}</math> jest dwukolorowalna, 
jeśli istnieje podzbiór <math>C\subseteq X</math> taki, że


<center><math>\emptyset\neq C \cap A \neq A\quad\text{dla każdego}\ A\in\mathcal{X}</math></center>


{{twierdzenie|3.8|tw 3.8|
Niech <math>n\geq 1</math> oraz <math>\mathcal{X}\subseteq \mathcal{P}_{n}\!\left( X \right)</math>.
Jeśli <math>\left\vert X \right\vert < 2^{n-1}</math>, to rodzina <math>\mathcal{X}</math> jest dwukolorowalna.
}}

{{dowod|||
Niech <math>m:=\left\vert X \right\vert</math>. Policzmy  pary w zbiorze


<center><math>\mathcal{A}=\left\lbrace \left( A,C \right):\ A\in\mathcal{X} \mbox{ i } \left( A\subseteq C \mbox{ albo } A\subseteq X- C \right) \right\rbrace</math></center>


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


<center><math>\left\vert \mathcal{A} \right\vert=\left\vert \mathcal{X} \right\vert\cdot 2^{m-n+1}</math></center>


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


<center><math>2^m\leq\left\vert \mathcal{A} \right\vert=\left\vert \mathcal{X} \right\vert\cdot 2^{m-n+1}</math>,</center>


skąd natychmiast


<center><math>\left\vert \mathcal{X} \right\vert\geq 2^{n-1}</math></center>


}}

{{twierdzenie|3.9 [P. Erd{o}s 1947]|tw 3.9|

<center><math>\mathsf{ R}\!\left( n,n \right)\geq n2^{n/2}\left( \frac{1}{e\sqrt{2}}-o\left( 1 \right) \right)</math></center>


}}

{{dowod|||
Niech <math>Y</math> będzie zbiorem o <math>m:=\mathsf{ R}\!\left( n,n \right)</math> elementach. 
Połóżmy 


<center><math>X=\mathcal{P}_{2}\!\left( Y \right)
</math></center>


i dalej 


<center><math>\mathcal{X}=\left\lbrace \mathcal{P}_{2}\!\left( A \right):\ A\in\mathcal{P}_{n}\!\left( Y \right) \right\rbrace. 
</math></center>


Wtedy <math>\mathcal{X}\subseteq\mathcal{P}_{{n\choose2}}\!\left( X \right)</math>. 
Ponieważ <math>Y</math> ma <math>\mathsf{ R}\!\left( n,n \right)</math> elementów, 
to rodzina <math>\mathcal{X}</math> nie jest dwukolorowalna, 
tak więc na mocy [[#tw_3.8|Twierdzenia 3.8]] trzymujemy:


<center><math>\left\vert \mathcal{X} \right\vert\geq 2^{{n\choose 2}-1}
</math></center>


Z kolei definicja rodziny <math>\mathcal{X}</math> daje <math>\left\vert \mathcal{X} \right\vert={m\choose n}</math>, 
a więc


<center><math>\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 \mathcal{X} \right\vert
\geq 2^{{n\choose 2}-1}
</math></center>


Otrzymujemy więc, że


<center><math>m^n\geq n!\cdot2^{\left( n^2-n-2 \right)/2}</math>,</center>


co z kolei implikuje, że


<center><math>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)</math></center>


Oszacowanie Sterlinga na <math>n!</math> daje 


<center><math>\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)</math></center>


i w konsekwencji otrzymujemy:


<center><math>\mathsf{ 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)</math></center>


}}

[[#tw_3.3|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]|tw 3.10|
Dla dowolnych dwóch grafów prostych <math>\mathbf{H}_1</math> oraz <math>\mathbf{H}_2</math> 
istnieje graf prosty <math>\mathbf{G}</math> taki, 
że jakkolwiek nie podzielimy zbioru krawędzi <math>\mathsf{ E}\!\left(\mathbf{G}\right)</math> na zbiory <math>E_1,E_2</math>, 
to <math>\mathbf{H}_1</math> będzie podgrafem indukowanym grafu <math>\left( \mathsf{ V}\!\left(\mathbf{G}\right),E_1 \right)</math> 
lub <math>\mathbf{H}_2</math> będzie podgrafem indukowanym grafu <math>\left( \mathsf{ V}\!\left(\mathbf{G}\right),E_2 \right)</math>.
}}