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 3.1 [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 3.1.

Twierdzenie 3.2 [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{oraz}\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 3.3 [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 $x\in \mathsf{V}\left(\mathbf{𝐆}\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$:

$\begin{array}{rl}{\mathsf{N}}_{\mathbf{𝐆}}\left(x\right)& =\{y\in \mathsf{V}\left(\mathbf{𝐆}\right):xy\in \mathsf{E}\left(\mathbf{𝐆}\right)\},\\ {\mathsf{A}}_{\mathbf{𝐆}}\left(x\right)& =\{y\in \mathsf{V}\left(\mathbf{𝐆}\right):xy\notin \mathsf{E}\left(\mathbf{𝐆}\right)\}.\end{array}$

Zdefiniujemy ciąg grafów ${\mathbf{𝐆}}_0,{\mathbf{𝐆}}_1,\dots ,{\mathbf{𝐆}}_{2r-1}$. Niech ${\mathbf{𝐆}}_0:=\mathbf{𝐆}$. Wybierzmy jakiś element $x_1\in \mathsf{V}\left(\mathbf{𝐆}\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}|_{\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{array} \right. }

Zauważmy, że $\left|\mathsf{V}\left({\mathbf{𝐆}}_1\right)\right|\ge 2^{2r-2}$. Następnie wybieramy dowolny element $x_2\in \mathsf{V}\left({\mathbf{𝐆}}_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}}|_{\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{array} \right. }

gdzie $x_{i-1}$ jest dowolnie wybranym elementem ze zbioru $\mathsf{V}\left({\mathbf{𝐆}}_{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|\mathsf{V}\left({\mathbf{𝐆}}_i\right)\right|\ge 2^{2r-(i+1)}.$

To z kolei implikuje, że dla $i\le 2r-1$ zbiór $\mathsf{V}\left({\mathbf{𝐆}}_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 $\mathsf{V}\left({\mathbf{𝐆}}_{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 $\mathsf{V}\left({\mathbf{𝐆}}_{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 3.2), jak i Twierdzenie 3.3 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 3.3 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ń 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{\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 ${\mathsf{R}}_r(q_1,\dots ,q_t)$ to najmniejsza taka liczba $n\in \mathbb{\mathbb{N}}$, dla której spełniony jest warunek $(*)$.
Szczególnym przypadkiem jest $\mathsf{R}(q_1,\dots ,q_t):={\mathsf{R}}_2(q_1,\dots ,q_t)$.

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

$\begin{array}{ccccccccc}n\downarrow m\to & 2& 3& 4& 5& 6& 7& 8& 9\\ HLINE\; TBD2& 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& & & \end{array}$

Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a $\mathsf{R}(q_1,\dots ,q_t)$ 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:

${\mathsf{R}}_1(q_1,\dots ,q_t)=\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

$\mathsf{R}(q_1,\dots ,q_t)\le \frac{t^{q_1+\dots +q_t-2t+1}-1}{t-1}+1.$

Z uwagi na Twierdzenie 3.3, ważną rolę odgrywają liczby Ramsey'a postaci ${\mathsf{R}}_r(m,n)$ a w szczególności $\mathsf{R}(m,n)={\mathsf{R}}_2(m,n)$. O nich możemy powiedzieć już trochę więcej w tym wykładzie.

Twierdzenie 3.6

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

${\mathsf{R}}_r(m,n)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_r(m-1,n),{\mathsf{R}}_r(m,n-1))+1.$

Dowód

Niech $X$ będzie zbiorem o ${\mathsf{R}}_{r-1}({\mathsf{R}}_r(m-1,n),{\mathsf{R}}_r(m,n-1))+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 „\begin{align}”): {\displaystyle \begin{align} \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. \end{align}}

Ponieważ moc $|X-\left\{x_0\right\}|$ realizuje liczbę Ramsey'a ${\mathsf{R}}_{r-1}({\mathsf{R}}_r(m-1,n),{\mathsf{R}}_r(m,n-1))$, to w zbiorze $X-\left\{x_0\right\}$

• istnieje podzbiór $X_1\subseteq X-\left\{x_0\right\}$ o mocy $\left|X_1\right|={\mathsf{R}}_r(m-1,n)$, 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 $\left|X_2\right|={\mathsf{R}}_r(m,n-1)$, 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 $\left|X_1\right|={\mathsf{R}}_r(m-1,n)$ 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 ${\mathsf{R}}_{r-1}({\mathsf{R}}_r(m-1,n),{\mathsf{R}}_r(m,n-1))+1$, to

${\mathsf{R}}_r(m,n)\le {\mathsf{R}}_{r-1}({\mathsf{R}}_r(m-1,n),{\mathsf{R}}_r(m,n-1))+1.$

Twierdzenie 3.7

Dla dowolnych $m,n\ge 2$

$\mathsf{R}(m,n)\le (\genfrac{}{}{0ex}{}{m+n-2}{m-1}).$

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na $n$ oraz $m$. Dla $n=2$ zachodzi równość

$\mathsf{R}(m,2)=m=(\genfrac{}{}{0ex}{}{m}{1})=(\genfrac{}{}{0ex}{}{m+n-2}{m-1}),$

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

$\mathsf{R}(2,n)=n=(\genfrac{}{}{0ex}{}{n}{1})=(\genfrac{}{}{0ex}{}{m+n-2}{m-1}).$

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

$\mathsf{R}(m-1,n)\le (\genfrac{}{}{0ex}{}{m+n-3}{m-2}),\mathsf{R}(m,n-1)\le (\genfrac{}{}{0ex}{}{m+n-3}{m-1}).$

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

${\mathsf{R}}_2(m,n)\le {\mathsf{R}}_1({\mathsf{R}}_2(m-1,n),{\mathsf{R}}_2(m,n-1))+1={\mathsf{R}}_2(m-1,n)+{\mathsf{R}}_2(m,n-1).$

Tak więc

$\begin{array}{rl}\mathsf{R}(m,n)& \le \mathsf{R}(m-1,n)+\mathsf{R}(m,n-1)\\ & \le (\genfrac{}{}{0ex}{}{m+n-3}{m-2})+(\genfrac{}{}{0ex}{}{m+n-3}{m-1})\\ & =(\genfrac{}{}{0ex}{}{m+n-2}{m-1}),\end{array}$

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\text{dla każdego}\ A\in\mathscr{X}. }

Twierdzenie 3.8

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 3.9 [P. Erd{o}s 1947]

$\mathsf{R}(n,n)\ge n{2}^{n/2}(\frac{1}{e\sqrt{2}}-o\left(1\right)).$

Dowód

Niech $Y$ będzie zbiorem o $m:=\mathsf{R}(n,n)$ 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 $\mathsf{R}(n,n)$ 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 3.8 trzymujemy:

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:

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

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