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

${\mathbf{𝐆}}_1=\{\begin{array}{ll}{\mathbf{𝐆}}_0{|}_{{\mathsf{N}}_{{\mathbf{𝐆}}_0}\left(x_1\right)},& \text{jeżeli}\left|{\mathsf{A}}_{{\mathbf{𝐆}}_0}\left(x_1\right)\right|\le \left|{\mathsf{N}}_{{\mathbf{𝐆}}_0}\left(x_1\right)\right|,\\ {\mathbf{𝐆}}_0{|}_{{\mathsf{A}}_{{\mathbf{𝐆}}_0}\left(x_1\right)},& \text{w przeciwnym wypadku.}\end{array}$

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

${\mathbf{𝐆}}_i=\{\begin{array}{ll}{\mathbf{𝐆}}_{i-1}{|}_{{\mathsf{N}}_{{\mathbf{𝐆}}_{i-1}}\left(x_i\right)},& \text{jeżeli}\left|{\mathsf{A}}_{{\mathbf{𝐆}}_{i-1}}\left(x_i\right)\right|\le \left|{\mathsf{N}}_{{\mathbf{𝐆}}_{i-1}}\left(x_i\right)\right|,\\ {\mathbf{𝐆}}_{i-1}{|}_{{\mathsf{A}}_{{\mathbf{𝐆}}_{i-1}}\left(x_i\right)},& \text{w przeciwnym wypadku,}\end{array}$

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 ${{𝒫}}_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 ${{𝒫}}_1\left(X\right)={{𝒜}}_1\cup \dots \cup {{𝒜}}_k$, gdzie ${{𝒜}}_i=\{\left\{x\right\}:x\in X_i\}$. 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 ${{𝒜}}_i$.

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

${{𝒫}}_r\left(X\right)={{𝒜}}_1\cup \dots \cup {{𝒜}}_t$, istnieje podzbiór $Y$ zbioru $X$ o co najmniej $q_i$ elementach taki, że ${{𝒫}}_r\left(Y\right)\subseteq {{𝒜}}_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ł ${{𝒫}}_r\left(X\right)={{𝒜}}_1\cup {{𝒜}}_2$ indukuje podział ${{𝒫}}_{r-1}\left(X^{\prime }\right)={𝒜}{\text{'}}_1\cup {𝒜}{\text{'}}_2$, gdzie

$\begin{array}{rl}{𝒜}{\text{'}}_1& =\{A-\left\{x_0\right\}:A\in {{𝒜}}_1\mathrm{\&}{x}_0\in A\},\\ {𝒜}{\text{'}}_2& =\{A-\left\{x_0\right\}:A\in {{𝒜}}_2\mathrm{\&}{x}_0\in A\}.\end{array}$

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 ${𝒜}{\text{'}}_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 ${𝒜}{\text{'}}_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 ${{𝒜}}_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 ${{𝒜}}_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 ${{𝒜}}_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 ${𝒜}{\text{'}}_1$. Z definicji rodziny ${𝒜}{\text{'}}_1$ otrzymujemy, że i w tym przypadku $A$ należy do ${{𝒜}}_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 ${{𝒜}}_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 ${{𝒜}}_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 ${𝒳}\subseteq {{𝒫}}_n\left(X\right)$, dla której istnieje takie kolorowanie elementów zbioru $X$ dwoma kolorami tak, by żaden zbiór $A\in {𝒳}$ nie składał się z elementów tego samego koloru.
Innymi słowy, rodzina ${𝒳}$ jest dwukolorowalna, jeśli istnieje podzbiór $C\subseteq X$ taki, że

$\mathrm{\varnothing }\ne C\cap A\ne A\text{dla każdego}A\in {𝒳}$

Twierdzenie 3.8

Niech $n\ge 1$ oraz ${𝒳}\subseteq {{𝒫}}_n\left(X\right)$. Jeśli $\left|X\right|<2^{n-1}$, to rodzina ${𝒳}$ jest dwukolorowalna.

Dowód

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

${𝒜}=\{(A,C):A\in {𝒳}\text{ i }(A\subseteq C\text{ albo }A\subseteq X-C)\}$

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

$\left|{𝒜}\right|=\left|{𝒳}\right|\cdot 2^{m-n+1}$

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

$2^m\le \left|{𝒜}\right|=\left|{𝒳}\right|\cdot 2^{m-n+1}$,

skąd natychmiast

$\left|{𝒳}\right|\ge 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

$X={{𝒫}}_2\left(Y\right)$

i dalej

${𝒳}=\{{{𝒫}}_2\left(A\right):A\in {{𝒫}}_n\left(Y\right)\}.$

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

$\left|{𝒳}\right|\ge 2^{(\genfrac{}{}{0ex}{}{n}{2})-1}$

Z kolei definicja rodziny ${𝒳}$ daje $\left|{𝒳}\right|=(\genfrac{}{}{0ex}{}{m}{n})$, a więc

$\frac{m^n}{n!}\ge \frac{m\cdot (m-1)\cdot \dots \cdot (m-n+1)}{n\cdot (n-1)\cdot \dots \cdot 1}=(\genfrac{}{}{0ex}{}{m}{n})=\left|{𝒳}\right|\ge 2^{(\genfrac{}{}{0ex}{}{n}{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)$.