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 $\mathbf{𝐆}=(V,E)$ jest spójny, potrzeba by miał on więcej niż $\left|V\right|\cdot (\left|V\right|-1)/2$ krawędzi. Najprostszym jednak warunkiem tego typu jest Zasada Szufladkowa Dirichleta i następujące jej uogólnienie.

Twierdzenie Uogólniona Zasada Szufladkowa Dirchlet'a

Dla dowolnej liczby $q\in \mathbb{\mathbb{N}}$, jeśli $X=X_1\cup \dots \cup X_t$ oraz $\left|X\right|\ge (q-1)t+1$, to dla któregoś $i$ mamy $\left|X_i\right|\ge q$.

Dowód

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

$(q-1)t+1\le \left|X\right|=|X_1\cup \dots \cup X_t|\le \left|X_1\right|+\dots +\left|X_t\right|\le t\cdot \underset{i=1,\dots ,t}{\max }\left|X_i\right|.$

Tak więc

$(q-1)+\frac{1}{t}=\frac{(q-1)t+1}{t}\le \underset{i=1,\dots ,t}{\max }\left|X_i\right|.$

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,\dots ,q_k$, w miejsce jednej liczby $q$, i podział $X=X_1\cup \dots \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 Uzupelnic th pigeon hall|.

Twierdzenie Zasada podziałowa

Niech $q_1,\dots ,q_k$ będzie ciągiem liczb naturalnych. Jeśli

$X=X_1\cup \dots \cup X_t\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}\left|X\right|>\left(\sum _{i=1}^t{q}_i\right)-t,$

to $\left|X_i\right|\ge q_i$ dla pewnego $i$.

Dowód

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

$\left(\sum _{i=1}^t{q}_i\right)-t+1\le \left|X\right|=|X_1\cup \dots \cup X_t|\le \left|X_1\right|+\dots +\left|X_t\right|\le \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 F.P.Ramsey 1930

Dla dowolnej liczby $r\in \mathbb{\mathbb{N}}$, jeżeli tylko graf prosty $\mathbf{𝐆}$ posiada co najmniej $2^{2r-1}$ elementów, to $\mathbf{𝐆}$ zawiera jako podgraf indukowany klikę ${{𝒦}}_r$ lub antyklikę ${{𝒜}}_r$.

Dowód

Niech $n:=\left|\mathbf{𝐆}\right|\ge 2^{2r-1}$. Dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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{𝐆}}_0,{\mathbf{𝐆}}_1,\dots ,{\mathbf{𝐆}}_{2r-1}$. Niech ${\mathbf{𝐆}}_0:=\mathbf{𝐆}$. Wybierzmy jakiś element Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_1\in{\sf V}\!\left(\mathbf{G}\right)} i zdefiniujmy podgraf ${\mathbf{𝐆}}_1$ grafu ${\mathbf{𝐆}}_0=\mathbf{𝐆}$ w następujący sposób

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}_1\right) \right\vert\geq2^{2r-2}} . Następnie wybieramy dowolny element Parser nie mógł rozpoznać (błąd składni): {\displaystyle x_2\in{\sf V}\!\left(\mathbf{G}_1\right)} i analogicznie definiujemy ${\mathbf{𝐆}}_2$. W ogólności dla $i=1,\dots ,2r-1$ graf ${\mathbf{𝐆}}_i$ definiujemy poprzez

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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ść

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert {\sf V}\!\left(\mathbf{G}_i\right) \right\vert\geq2^{2r-(i+1)}. }

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

Zauważmy, że zarówno Zasadę Podziałową ( Twierdzenie Uzupelnic th div law|), jak i Twierdzenie Uzupelnic th Ramsey graph| można wypowiedzieć w tym samym języku. Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{r}\!\left( X \right)} będzie rodziną $r$-elementowych podzbiorów zbioru $X$. Tak więc pokrycie $X=X_1\cup \dots \cup X_k$ to nic innego jak pokrycie rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{1}\!\left( X \right)=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_k} , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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|Y\right|=q_i$ oraz że dowolny singleton zawarty w $Y$ należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_i} .

Z drugiej strony graf prosty z Twierdzenia Uzupelnic th Ramsey graph| to para $\mathbf{𝐆}=(V,E)$, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle E\subseteq\mathscr{P}_{2}\!\left( V \right)} . Daje to więc podział Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{2}\!\left( K \right)} , jest $E$. Analogicznie poszukiwana antyklika jest po prostu podzbiorem $A$ zbioru $V$ takim, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{2}\!\left( A \right)\subseteq \mathscr{P}_{2}\!\left( V \right)- E} .

Następne twierdzenie jest uogólnieniem Twierdzeń Uzupelnic th pigeon hall|, Uzupelnic th div law|, oraz Uzupelnic th Ramsey graph|. 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 F. P. Ramsey 1930

Dla dowolnych $r,t\in \mathbb{\mathbb{N}}$ oraz dla dowolnego ciągu liczb naturalnych $q_1,\dots ,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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{r}\!\left( Y \right)\subseteq \mathscr{A}_i} przy pewnym $i=1,\dots ,t$.

Liczba Ramseya Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}_{r}\!\left( q_1,\ldots,q_t \right)} to najmniejsza taka liczba $n\in \mathbb{\mathbb{N}}$, dla której spełniony jest warunek $(*)$.
Szczególnym przypadkiem jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}_{2}\!\left( m,n \right)} . Jak widać nawet dla małych wartości $n$ oraz $m$, dokładne wartości liczb Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}_{2}\!\left( m,n \right)} nie są znane.

Uzupelnij tytul

$n\downarrow m\to$ || $2$ || $3$ || $4$ || $5$ || $6$ || $7$ || $8$ || $9$

$2$ || $2$ || $3$ || $4$ || $5$ || $6$ || $7$ || $8$ || $9$

$3$ || || $6$ || $9$ || $14$ || $18$ || $23$ || $28\le \dots \le 29$ || $36$

$4$ || || || $18$ || $25\dots \le 29$ || $34\le \dots \le 36$ || || ||

$4$ || || || || $42\le \dots \le 55$ || $57\le \dots \le 94$ || || ||

$4$ || || || || || $102\le \dots \le 178$ || || ||

Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Uzupelnic th div law|). Zasadę tę można przeformułować jako:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Uzupelnic th Ramsey graph|, ważną rolę odgrywają liczby Ramsey'a postaci Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}_{r}\!\left( m,n \right)} a w szczególności Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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

Dla dowolnych $m,n\ge 2$ oraz $r\ge 1$ mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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^{\prime }=X-\left\{x_0\right\}$. Wtedy każdy podział Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{r}\!\left( X \right)=\mathscr{A}_1\cup\mathscr{A}_2} indukuje podział Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{P}_{r-1}\!\left( X' \right)=\mathscr{A}'_1\cup\mathscr{A}'_2} , gdzie

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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 $|X-\left\{x_0\right\}|$ realizuje liczbę Ramsey'a Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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\{x_0\right\}$

• istnieje podzbiór $X_1\subseteq X-\left\{x_0\right\}$

o mocy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}'_1} ,

lub też

• istnieje podzbiór $X_2\subseteq X-\left\{x_0\right\}$

o mocy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}'_2} .

Bez straty ogólności załóżmy, że zachodzi przypadek pierwszy. Z definicji liczb Ramsey'a oraz z faktu, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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|X_{11}\right|=m-1$, i którego każdy $r$-elementowy podzbiór należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_1} .

• W $X_1$ istnieje podzbiór $X_{12}\subseteq X_1$,

o mocy $\left|X_{12}\right|=n$, i którego każdy $r$-elementowy podzbiór należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_2} .

Z uwagi na symetrię przeanalizujemy jedynie pierwszy przypadek. Niech $A\subseteq X_{11}\cup \left\{x_0\right\}$ ma $r$-elementów. Jeśli $x_0\in ̸A$, to $A$ zawiera się w $X_{11}$, i co za tym idzie, $A$ należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_1} . Jeśli zaś $x_0\in A$, to $A-\left\{x_0\right\}$ jest $(r-1)$-elementowym podzbiorem zbioru $X_1$. A więc należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}'_1} . Z definicji rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}'_1} otrzymujemy, że i w tym przypadku $A$ należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_1} .

W konsekwencji otrzymujemy, że w $X$ istnieje podzbiór $Y_1$ (w rozpatrzonym przypadku jest to $X_{11}\cup \left\{x_0\right\}$), którego każdy $r$-elementowy podzbiór należy do Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}_2} . Ponieważ zbiór $X$ ma moc Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}_{{r-1}}\!\left( {\sf R}_{r}\!\left( m-1,n \right),{\sf R}_{r}\!\left( m,n-1 \right) \right)+1} , to

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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. }

Twierdzenie

Dla dowolnych $m,n\ge 2$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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ść

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}\!\left( m,2 \right)=m={{m}\choose{1}}={{m+n-2}\choose{m-1}}, }

a dla $m=2$ zachodzi równość

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Uzupelnic th rec upper bound| mówi, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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.

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle A\in\mathscr{X}} nie składał się z elementów tego samego koloru.
Innymi słowy, rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}} jest dwukolorowalna, jeśli istnieje podzbiór $C\subseteq X$ taki, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \emptyset\neq C \cap A \neq A\quad\textrm{dla każdego}\ A\in\mathscr{X}. }

Twierdzenie

Niech $n\ge 1$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}\subseteq \mathscr{P}_{n}\!\left( X \right)} . Jeśli $\left|X\right|<2^{n-1}$, to rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}} jest dwukolorowalna.

Dowód

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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|A\right|=n$, to wynosi ona $2^{m-n}$. Zatem

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert \mathscr{A} \right\vert=\left\vert \mathscr{X} \right\vert\cdot 2^{m-n+1}. }

Niech teraz rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}} nie będzie dwukolorowalna, czyli dla każdego zbioru $C\subseteq X$ istnieje Parser nie mógł rozpoznać (błąd składni): {\displaystyle A\in\mathscr{X}} taki, że $A\subseteq C$ albo $A\subseteq X-C$. Tak więc par w Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{A}} jest co najmniej tyle co podzbiorów $C\subseteq X$, a więc

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2^m\leq\left\vert \mathscr{A} \right\vert=\left\vert \mathscr{X} \right\vert\cdot 2^{m-n+1}, }

skąd natychmiast

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert \mathscr{X} \right\vert\geq 2^{n-1}. }

Twierdzenie P. Erd{o}s 1947

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle m:={\sf R}\!\left( n,n \right)} elementach. Połóżmy

Parser nie mógł rozpoznać (błąd składni): {\displaystyle X=\mathscr{P}_{2}\!\left( Y \right) }

i dalej

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}=\left\lbrace \mathscr{P}_{2}\!\left( A \right):\ A\in\mathscr{P}_{n}\!\left( Y \right) \right\rbrace. }

Wtedy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}\subseteq\mathscr{P}_{{n\choose2}}\!\left( X \right)} . Ponieważ $Y$ ma Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf R}\!\left( n,n \right)} elementów, to rodzina Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}} nie jest dwukolorowalna, tak więc na mocy Twierdzenia Uzupelnic th two color| otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert \mathscr{X} \right\vert\geq 2^{{n\choose 2}-1} }

Z kolei definicja rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathscr{X}} daje Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert \mathscr{X} \right\vert={m\choose n}} , a więc

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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\ge n!\cdot 2^{(n^2-n-2)/2},$

co z kolei implikuje, że

$m\ge \sqrt[n]{n!}\cdot 2^{n/2}\cdot 2^{-1/2}\cdot 2^{-1/n}\ge \sqrt[n]{n!}\cdot 2^{n/2}(\frac{1}{\sqrt{2}}-o\left(1\right)).$

Oszacowanie Sterlinga na $n!$ daje

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

i w konsekwencji otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\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). }

Twierdzenie Uzupelnic th Ramsey graph| ma jeszcze inne ciekawe uogólnienie, pozwalające na wyszukiwanie zadanych uprzednio podgrafów w grafie macierzystym.

Twierdzenie W. Deuber 1974

Dla dowolnych dwóch grafów prostych ${\mathbf{𝐇}}_1$ oraz ${\mathbf{𝐇}}_2$ istnieje graf prosty $\mathbf{𝐆}$ taki, że jakkolwiek nie podzielimy zbioru krawędzi Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\sf E}\!\left(\mathbf{G}\right)} na zbiory $E_1,E_2$, to ${\mathbf{𝐇}}_1$ będzie podgrafem indukowanym grafu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}\right),E_1 \right)} lub ${\mathbf{𝐇}}_2$ będzie podgrafem indukowanym grafu Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left( {\sf V}\!\left(\mathbf{G}\right),E_2 \right)} .