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 {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$.

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 {\text{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.

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 {\mathsf {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$:

${\begin{aligned}{\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{aligned}}$

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 {\mathsf {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}={\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}}$

Zauważmy, że $\left\vert {\mathsf {V}}\!\left(\mathbf {G} _{1}\right)\right\vert \geq 2^{2r-2}$. Następnie wybieramy dowolny element $x_{2}\in {\mathsf {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}={\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}}$

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

To z kolei implikuje, że dla $i\leq 2r-1$ zbiór ${\mathsf {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 ${\mathsf {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 ${\mathsf {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.

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 ${\mathcal {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 ${\mathcal {P}}_{1}\!\left(X\right)={\mathcal {A}}_{1}\cup \ldots \cup {\mathcal {A}}_{k}$, gdzie ${\mathcal {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 ${\mathcal {A}}_{i}$.

Z drugiej strony graf prosty z Twierdzenia 3.3 to para $\mathbf {G} =\left(V,E\right)$, gdzie $E\subseteq {\mathcal {P}}_{2}\!\left(V\right)$. Daje to więc podział ${\mathcal {P}}_{2}\!\left(V\right)=E\cup \left({\mathcal {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 ${\mathcal {P}}_{2}\!\left(K\right)$, jest $E$. Analogicznie poszukiwana antyklika jest po prostu podzbiorem $A$ zbioru $V$ takim, że ${\mathcal {P}}_{2}\!\left(A\right)\subseteq {\mathcal {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

${\mathcal {P}}_{r}\!\left(X\right)={\mathcal {A}}_{1}\cup \ldots \cup {\mathcal {A}}_{t}$, istnieje podzbiór $Y$ zbioru $X$ o co najmniej $q_{i}$ elementach taki, że ${\mathcal {P}}_{r}\!\left(Y\right)\subseteq {\mathcal {A}}_{i}$ przy pewnym $i=1,\ldots ,t$.

Liczba Ramseya ${\mathsf {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 ${\mathsf {R}}\!\left(q_{1},\ldots ,q_{t}\right):={\mathsf {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 ${\mathsf {R}}_{2}\!\left(m,n\right)$. Jak widać nawet dla małych wartości $n$ oraz $m$, dokładne wartości liczb ${\mathsf {R}}_{2}\!\left(m,n\right)$ nie są znane.

${\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 \leq 29&36\\\hline 4&&&18&25\ldots \leq 29&34\leq \ldots \leq 36&&&\\\hline 4&&&&42\leq \ldots \leq 55&57\leq \ldots \leq 94&&&\\\hline 4&&&&&102\leq \ldots \leq 178&&&\\\hline \end{array}}$

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

${\mathsf {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

${\mathsf {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 ${\mathsf {R}}_{r}\!\left(m,n\right)$ a w szczególności ${\mathsf {R}}\!\left(m,n\right)={\mathsf {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:

${\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$

Dowód

Niech $X$ będzie zbiorem o ${\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r}\!\left(m-1,n\right),{\mathsf {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ł ${\mathcal {P}}_{r}\!\left(X\right)={\mathcal {A}}_{1}\cup {\mathcal {A}}_{2}$ indukuje podział ${\mathcal {P}}_{r-1}\!\left(X'\right)={\mathcal {A}}'_{1}\cup {\mathcal {A}}'_{2}$, gdzie

${\begin{aligned}{\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{aligned}}$

Ponieważ moc $\left\vert X-\left\lbrace x_{0}\right\rbrace \right\vert$ realizuje liczbę Ramsey'a ${\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r}\!\left(m-1,n\right),{\mathsf {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 ={\mathsf {R}}_{r}\!\left(m-1,n\right)$, w którym dowolny podzbiór $(r-1)$-elementowy należy do ${\mathcal {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 ={\mathsf {R}}_{r}\!\left(m,n-1\right)$, w którym dowolny podzbiór $(r-1)$-elementowy należy do ${\mathcal {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 ={\mathsf {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 ${\mathcal {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 ${\mathcal {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 ${\mathcal {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 ${\mathcal {A}}'_{1}$. Z definicji rodziny ${\mathcal {A}}'_{1}$ otrzymujemy, że i w tym przypadku $A$ należy do ${\mathcal {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 ${\mathcal {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 ${\mathcal {A}}_{2}$. Ponieważ zbiór $X$ ma moc ${\mathsf {R}}_{r-1}\!\left({\mathsf {R}}_{r}\!\left(m-1,n\right),{\mathsf {R}}_{r}\!\left(m,n-1\right)\right)+1$, to

${\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$

Twierdzenie 3.7

Dla dowolnych $m,n\geq 2$

${\mathsf {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ść

${\mathsf {R}}\!\left(m,2\right)=m={{m} \choose {1}}={{m+n-2} \choose {m-1}}$,

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

${\mathsf {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:

${\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}}$

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

${\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)$

Tak więc

${\begin{aligned}{\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{aligned}}$

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

$\emptyset \neq C\cap A\neq A\quad {\text{dla każdego}}\ A\in {\mathcal {X}}$

Twierdzenie 3.8

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

Dowód

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

${\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$

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

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

$2^{m}\leq \left\vert {\mathcal {A}}\right\vert =\left\vert {\mathcal {X}}\right\vert \cdot 2^{m-n+1}$,

skąd natychmiast

$\left\vert {\mathcal {X}}\right\vert \geq 2^{n-1}$

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

${\mathsf {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:={\mathsf {R}}\!\left(n,n\right)$ elementach. Połóżmy

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

i dalej

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

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

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

Z kolei definicja rodziny ${\mathcal {X}}$ daje $\left\vert {\mathcal {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 {\mathcal {X}}\right\vert \geq 2^{{n \choose 2}-1}$

Otrzymujemy więc, że

$m^{n}\geq n!\cdot 2^{\left(n^{2}-n-2\right)/2}$,

co z kolei implikuje, że

$m\geq {\sqrt[{n}]{n!}}\cdot 2^{n/2}\cdot 2^{-1/2}\cdot 2^{-1/n}\geq {\sqrt[{n}]{n!}}\cdot 2^{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:

${\mathsf {R}}\!\left(n,n\right)=m\geq {\sqrt[{n}]{n!}}\cdot 2^{n/2}\left({\frac {1}{\sqrt {2}}}-o\left(1\right)\right)\geq n\cdot 2^{n/2}\left({\frac {1}{e{\sqrt {2}}}}-o\left(1\right)\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 {H} _{1}$ oraz $\mathbf {H} _{2}$ istnieje graf prosty $\mathbf {G}$ taki, że jakkolwiek nie podzielimy zbioru krawędzi ${\mathsf {E}}\!\left(\mathbf {G} \right)$ na zbiory $E_{1},E_{2}$, to $\mathbf {H} _{1}$ będzie podgrafem indukowanym grafu $\left({\mathsf {V}}\!\left(\mathbf {G} \right),E_{1}\right)$ lub $\mathbf {H} _{2}$ będzie podgrafem indukowanym grafu $\left({\mathsf {V}}\!\left(\mathbf {G} \right),E_{2}\right)$.