01ZTGA:Kapitola2 4
Z WikiSkripta FJFI ČVUT v Praze
Verze z 15. 1. 2012, 15:18, kterou vytvořil Karel.brinda (diskuse | příspěvky)
[ znovu generovat, | výstup z překladu ] | Kompletní WikiSkriptum včetně všech podkapitol. | |
PDF Této kapitoly | [ znovu generovat, | výstup z překladu ] | Přeložení pouze této kaptioly. |
ZIP | Kompletní zdrojový kód včetně obrázků. |
Součásti dokumentu 01ZTGA
součást | akce | popis | poslední editace | soubor | |||
---|---|---|---|---|---|---|---|
Hlavní dokument | editovat | Hlavní stránka dokumentu 01ZTGA | Karel.brinda | 16. 1. 2012 | 00:45 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 14:51 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 13:34 | header.tex | |
Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 13:36 | cast0.tex | |
Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 13:46 | cast1_kapitola1.tex | |
Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 13:49 | cast1_kapitola2.tex | |
Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 13:50 | cast1_kapitola3.tex | |
Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 10:06 | cast1_kapitola4.tex | |
Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 13:51 | cast1_kapitola5.tex | |
Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 13:53 | cast1_kapitola6.tex | |
Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 14:34 | cast1_kapitola7.tex | |
Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 14:40 | cast1_kapitola8.tex | |
Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 14:44 | cast1_kapitola9.tex | |
Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:48 | cast1_kapitola10.tex | |
Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 14:52 | cast1_kapitola11.tex | |
Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 14:56 | cast1_kapitola12.tex | |
Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 14:57 | cast1_kapitola13.tex | |
Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 15:11 | cast2_kapitola1.tex | |
Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 15:12 | cast2_kapitola2.tex | |
Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 15:16 | cast2_kapitola3.tex | |
Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 15:18 | cast2_kapitola4.tex | |
Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 15:22 | cast3_kapitola1.tex | |
Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 15:22 | cast3_kapitola2.tex |
Zdrojový kód
%\wikiskriptum{01ZTGA} \section{Ramseyovská čísla} \begin{example} \label{exa:ramsey}Ve skupině $6$ lidí existuje trojice lidí taková, že se všichni navzájem znají nebo se všichni navzájem neznají. (V libovolném grafu na $6$ vrcholech existuje klika velikosti $3$ nebo nezávislá množina velikosti $3$.) \end{example} \begin{proof} Mohou nastat dvě možnosti: \begin{enumerate} \item Existuje vrchol $v$ stupně $\geq3$. Nechť z $v$ vedou hrany do vrcholů $v_{1},v_{2},v_{3}$. Potom pokud mezi nějakými vrcholy $v_{i},v_{j}$ ($i,j\in\{1,2,3\}$) vede hrana, tvoří vrcholy $v,v_{i},v_{j}$ kliku velikosti $3$. Naopak pokud mezi $v_{1},v_{2},v_{3}$ nevede žádná hrana, tvoří tyto vrcholy nezávislou množinu velikosti $3$. \item Všechny vrcholy mají stupeň $\leq2$. Vezměme libovolný vrchol $v$. Z něho \emph{ne}vedou hrany do alespoň $3$ vrcholů $v_{1},v_{2},v_{3}$. Potom pokud mezi nějakými vrcholy $v_{i},v_{j}$ ($i,j\in\{1,2,3\}$) nevede hrana, tvoří vrcholy $v,v_{i},v_{j}$ nezávislou množinu velikosti $3$. Naopak pokud mezi $v_{1},v_{2},v_{3}$ vedou všechny hrany, tvoří tyto vrcholy kliku velikosti $3$. \end{enumerate} \end{proof} \begin{thm} \textbf{\emph{(Ramsey)}} \[ \left(\forall k,l\in\N\right)\left(\exists n_{0}\in\N\right)\left(\forall n\geq n_{0}\right)\left(\forall G,\# V(G)=n\right)\left(\left(\omega(G)\geq k\right)\vee\left(\alpha(G)\geq l\right)\right).\] Slovy: Pro každé $k,l\in\N$ existuje $n_{0}\in\N$ takové, že každý graf na alespoň $n_{0}$ vrcholech obsahuje kliku velikosti $k$ \underbar{nebo} nezávislou množinu velikosti $l$. \end{thm} \begin{defn} Minimální $n_{0}$ z Ramseyovy věty pro daná $k,l$ značíme $r(k,l)$ a nazýváme jej \textbf{ramseyovským číslem}. \end{defn} \begin{rem*} V příkladě \ref{exa:ramsey} jsme vlastně našli pro $k=l=3$ číslo $n_{0}=6$, tj. ukázali jsme $r(3,3)\leq6$. Nemůže být ovšem $r(3,3)\leq5$. Příkladem grafu na $5$ vrcholech, pro který $\left(\omega(G)<3\right)\wedge\left(\alpha(G)<3\right)$, je cyklus $C_{5}$. Proto $r(3,3)=6$. \end{rem*} \begin{proof} (Ramseyovy věty) Budeme postupovat indukcí podle $\left(k+l\right)$. Předvedeme úvahu, která bude jen zobecněním důkazu v příkladě \ref{exa:ramsey}. Protože v indukčním kroku tvaru $\left(k+l\right)-1\to\left(k+l\right)$ budme potřebovat čísla $k-1$ i $l-1$, lze jej provést až pro $\left(k\geq2\right)\wedge\left(l\geq2\right)$. Na počátku tedy potřebujeme ověřit platnost tvrzení pro $k=1,l\in\N$ a pro $k\in\N,l=1$. Zřejmě však platí \begin{itemize} \item $r(k,1)=1$, \item $r(1,l)=1$. \end{itemize} Poznamenejme, že snadno je vidět rovněž \begin{itemize} \item $r(k,2)=k$, protože buď jsou v grafu $G$ na $k$ vrcholech všechny hrany, a tedy $K_{k}=G$, a nebo alespoň jedna chybí, ale potom je v $G$ nezávislá množina velikosti $2$. \item $r(2,l)=l$, protože buď v grafu $G$ na $l$ vrcholech nejsou žádné hrany, a tedy (v) $G$ je nezávislá množina velikosti $l$, nebo $G$ má alespoň jednu hranu, ale potom $G$ obsahuje $K_{2}$. \end{itemize} Indukční krok $\boxed{\left(k+l\right)-1\to\left(k+l\right)}$:Najdeme $n_{0}$ jako $n_{0}=r(k-1,l)+r(k,l-1)$ a ukážeme, že každý graf $G$ na $n=n_{0}$ (a tedy i na $n>n_{0}$) vrcholech obsahuje kliku velikosti $k$ nebo nezávislou množinu velikosti $l$. Mohou nastat dva případy: \begin{enumerate} \item Existuje vrchol $v\in V(G)$ tak, že $d_{G}(v)\geq r(k-1,l)$. Označme jako $H$ podgraf indukovaný množinou sousedů vrcholu $v$. Potom $\# V(H)\geq r(k-1,l)$. Podle indukčního předpokladu v $H$ existuje $K_{k-1}$, která však spolu s vrcholem $v$ tvoří kliku $K_{k}$ v grafu $G$, nebo v $H$ existuje nezávislá množina velikosti $l$, takže i v $G$ existuje nezávislá množina velikosti $l$. \item Všechny vrcholy grafu $G$ mají stupeň $<r(k-1,l)$. Nechť $v\in V(G)$. Potom $d_{G}(v)<r(k-1,l)\Rightarrow d_{G}(v)\leq r(k-1,l)-1$. To znamená, že existuje množina alespoň $n-1-\left(r(k-1,l)-1\right)=r(k,l-1)$ vrcholů, do nichž nevede hrana z vrcholu $v$. Označme jako $H$ podgraf indukovaný touto množinou vrcholů. Podle indukčního předpokladu v $H$ existuje nezávislá množina velikosti $l-1$, která však spolu s vrcholem $v$ tvoří nezávislou množinu velikosti $l$ v grafu $G$, nebo v $H$ existuje klika $K_{k}$, což znamená, že i v $G$ existuje $K_{k}$. \end{enumerate} \end{proof} \begin{rem} Protože k libovolnému grafu $\bar{G}$ na $n$ vrcholech existuje graf $G$ na $n$ vrcholech tak, že $\bar{G}$ je doplňkem $G$, lze tvrzení plynoucí z Ramseyovy věty, zapsané ve tvaru\[ \left(\forall k,l\in\N\right)\left(\forall n\geq r(k,l)\right)\left(\forall\bar{G},\# V(\bar{G})=n\right)\left(\left(\omega(\bar{G})\geq k\right)\vee\left(\alpha(\bar{G})\geq l\right)\right),\] přeformulovat na\[ \left(\forall k,l\in\N\right)\left(\forall n\geq r(k,l)\right)\left(\forall G,\# V(G)=n\right)\left(\left(\omega(\bar{G})\geq k\right)\vee\left(\alpha(\bar{G})\geq l\right)\right).\] To je podle známých rovností uvedených v poznámce \ref{rem:alfa-omega-v-doplnku-G} ekvivalentní s\[ \left(\forall k,l\in\N\right)\left(\forall n\geq r(k,l)\right)\left(\forall G,\# V(G)=n\right)\left(\left(\alpha(G)\geq k\right)\vee\left(\omega(G)\geq l\right)\right),\] což z definice ramseyovských čísel znamená $\left(\forall k,l\in\N\right)\left(r(l,k)\leq r(k,l)\right)$. To samozřejmě implikuje\[ \left(\forall k,l\in\N\right)\left(r(l,k)=r(k,l)\right).\] \end{rem} \begin{rem*} Není jednoduché hodnoty $r(k,l)$ vypočítat. Známé hodnoty ramseyovských čísel jsou uvedeny v tabulce \ref{cap:znama-r-kl}. Netriviální ramseyovská čísla jsou v pravém dolním čtverci. Hodnota $r(4,5)$ je známa od roku 1993. O hodnotě $r(5,5)$ víme pouze\[ 42\leq r(5,5)\leq50.\] % \begin{table} \begin{center}\begin{tabular}{|>{\centering}m{1cm}||c|c||c|c|c|c|c|} \hline %Title: rkl_table.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 15:20:24 1970 %%User: Pavel Strachota@DIGITHELL (DIGITHELL) \font\thinlinefont=cmr5 % \begingroup\makeatletter\ifx\SetFigFont\undefined% \gdef\SetFigFont#1#2#3#4#5{% \reset@font\fontsize{#1}{#2pt}% \fontfamily{#3}\fontseries{#4}\fontshape{#5}% \selectfont}% \fi\endgroup% \mbox{\beginpicture \setcoordinatesystem units <1.00000cm,1.00000cm> \unitlength=1.00000cm \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) \setshadesymbol ({\thinlinefont .}) \setlinear % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$l$}% } [lB] at 7.976 20.597 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$k$}% } [lB] at 7.144 20.123 % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 7.144 20.955 8.096 20.003 / }% \linethickness=0pt \putrectangle corners at 7.112 20.980 and 8.122 19.977 \endpicture} & 1& 2& 3& 4& 5& 6& 7\tabularnewline \hline \hline 1& 1& 1& 1& 1& 1& 1& 1\tabularnewline \hline 2& 1& 2& 3& 4& 5& 6& 7\tabularnewline \hline \hline 3& 1& 3& 6& 9& 14& 18& 23\tabularnewline \hline 4& 1& 4& 9& 17& 25& & \tabularnewline \hline 5& 1& 5& 14& 25& & & \tabularnewline \hline 6& 1& 6& 18& & & & \tabularnewline \hline 7& 1& 7& 23& & & & \tabularnewline \hline \end{tabular}\end{center} \caption{\label{cap:znama-r-kl}Známé hodnoty ramseyovských čísel} \end{table} \end{rem*} \subsection{Odhady ramseyovských čísel} \begin{rem} Z důkazu Ramseyovy věty plyne nerovnost\[ r(k-1,l)+r(k,l-1)\geq r(k,l),\] protože pro $n=r(k-1,l)+r(k,l-1)$ jsme již dokázali její tvrzení pro $k,l$. \end{rem} \begin{cor} \[ r(k,l)\leq\binom{k+l-2}{k-1}\] \end{cor} \begin{proof} Indukcí podle $\left(k+l\right)$. Uvedeme pouze indukční krok, platnost vztahu pro $k=1,l\in\N$ (a pro $k\in\N,l=1$) lze ověřit prostým dosazením.\[ r(k,l)\leq r(k-1,l)+r(k,l-1)\leq\binom{k-1+l-2}{k-2}+\binom{k+l-1-2}{k-1}=\binom{k+l-2}{k-1}.\] \end{proof} \begin{cor} \label{cor:horni-odhad-r-k-k}\[ r(k,k)\leq\binom{2k-2}{k-1}\leq4^{k-1}\] \end{cor} \begin{proof} Jedná se o dosazení $l=k$. Pokud jde o pravou nerovnost, platí\[ \binom{2n}{n}\leq\sum_{j=0}^{2n}\binom{2n}{j}=\sum_{j=0}^{2n}\binom{2n}{j}1^{j}1^{(2n-j)}=(1+1)^{2n}=4^{n},\] kde $\binom{2n}{n}$ je pouze poslední člen uvedené sumy. \end{proof} \begin{rem*} Ještě lepší odhad získáme použitím Stirlingovy formule:\[ \binom{2n}{n}=\frac{(2n)!}{n!^{2}}\approx\frac{(2n)^{2n}\e^{-2n}\sqrt{2\pi\cdot2n}}{n^{2n}\e^{-2n}\cdot2\pi n}\approx\frac{c}{\sqrt{n}}4^{n},\] takže po dosazení\[ r(k,k)\leq\frac{\tilde{c}}{\sqrt{k-1}}4^{k-1}=\frac{c}{\sqrt{k}}4^{k}.\] \end{rem*} \begin{thm} \label{thm:nerovnost-r-kl}Pro každé $k,l\in\N$ platí\[ r(kl+1,kl+1)-1\geq\left(r(k+1,k+1)-1\right)\left(r(l+1,l+1)-1\right).\] \end{thm} \begin{proof} Pro účely důkazu si definujeme \emph{kompozici} dvou grafů $G=(V,E)$ a $H=(U,F)$ jako graf\[ G[H]=(V\times U,\mathcal{E}),\] kde\[ \left\{ (v_{1},u_{1}),(v_{2},u_{2})\right\} \in\mathcal{E}\;\Leftrightarrow\;\left(\{ v_{1},v_{2}\}\in E\vee\left(v_{1}=v_{2}\wedge\{ u_{1},u_{2}\}\in F\right)\right).\] Graf $G[H]$ si můžeme představit jako graf $G$, kde každý vrchol $v_{i}\in V$ je nahrazen kopií grafu $H$ (,,knedlíkem{}``), kterou můžeme označit $H_{i}$. Vede-li mezi dvěma vrcholy $v_{i},v_{j}$ hrana v grafu $G$, pak v $G[H]$ vedou hrany mezi každými dvěma vrcholy $w_{1}\in H_{i},w_{2}\in H_{j}$. Pro $G[H]$ platí vztahy\begin{eqnarray*} \omega(G[H]) & = & \omega(G)\omega(H),\\ \alpha(G[H]) & = & \alpha(G)\alpha(H),\end{eqnarray*} které docela přímočaře využijeme při důkazu tvrzení věty. Nejprve ale pojďme ověřit jejich platnost. \begin{itemize} \item Počet ,,knedlíků{}``, ve kterých se vyskytuje nějaký vrchol z libovolné kliky v $G[H]$, je $\leq\omega(G)$. Dokážeme to (až zbytečně detailně) sporem. Nechť pro každé $i\in\hat{m},m>\omega(G)$ jsou $w_{i}\in H_{i}$ vrcholy z různých ,,knedlíků{}`` a nechť $\{ w_{1},...,w_{m}\}$ je součástí kliky v $G[H]$. Z předpokladu $m>\omega(G)$ vrcholy $\{ v_{1},...,v_{m}\}$ grafu $G$ příslušné ,,knedlíkům{}`` $\{ H_{1},...,H_{m}\}$ netvoří kliku. Proto $\exists i_{1},i_{2}\in\hat{m}$ takové, že $\{ v_{i_{1}},v_{i_{2}}\}\notin E$. To ale znamená, že mezi $H_{i_{1}}$ a $H_{i_{2}}$ nevedou hrany, takže $\{ w_{i_{1}},w_{i_{2}}\}\notin\mathcal{E}$, což je spor. \item Z jednoho ,,knedlíku{}`` se v libovolné klice v $G[H]$ může vyskytovat nejvýše $\omega(H)$ vrcholů. Důkaz je obdobný. Jestliže vybereme z jednoho ,,knedlíku{}`` $H_{i}$ více vrcholů, pak netvoří kliku v $H_{i}$, a tedy nemohou být součástí kliky v $G[H]$. \end{itemize} Tím jsme dokázali, že \begin{equation} \omega(G[H])\leq\omega(G)\omega(H).\label{eq:kompozice-nerovnost}\end{equation} Je však zřejmé, že vezmeme-li $H_{i}$ odpovídající vrcholům z maximální kliky v $G$ a v každém $H_{i}$ vybereme vrcholy tvořící maximální kliku v $H_{i}$, dostamene kliku v $G[H]$ velikosti právě rovné $\omega(G)\omega(H)$, a podle nerovnosti (\ref{eq:kompozice-nerovnost}) jde už o kliku maximální. Proto platí\[ \omega(G[H])=\omega(G)\omega(H).\] Druhý vztah pro velikosti nezávislé množiny se ověří naprosto stejným způsobem, v předchozích úvahách stačí slovo ,,klika{}`` nahradit slovem ,,nezávislá množina{}``. Nyní již ukážeme tvrzení věty. Z definice ramseyovských čísel $r(k,l)$ plyne: \begin{itemize} \item pro $r(k+1,k+1)-1$: Existuje graf $G$ na $r(k+1,k+1)-1$ vrcholech, pro který $\omega(G)<k+1$ a zároveň $\alpha(G)<k+1$. To znamená, že $\omega(G)\leq k,\alpha(G)\leq k$. \item pro $r(l+1,l+1)-1$: Existuje graf $H$ na $r(l+1,l+1)-1$ vrcholech, pro který $\omega(H)<l+1$ a zároveň $\alpha(H)<l+1$. To znamená, že $\omega(H)\leq l,\alpha(H)\leq l$. \end{itemize} Z toho plyne, že pro kompozici grafů $G,H$, tj. pro graf $G[H]$, platí \begin{itemize} \item $G[H]$ je graf na $\left(r(k+1,k+1)-1\right)\left(r(l+1,l+1)-1\right)$ vrcholech, \item $\omega(G[H])=\omega(G)\omega(H)\leq kl<kl+1$ \item $\alpha(G[H])=\alpha(G)\alpha(H)\leq kl<kl+1$ \end{itemize} Jinými slovy to znamená, že jsme našli graf na $\left(r(k+1,k+1)-1\right)\left(r(l+1,l+1)-1\right)$ vrcholech, který neobsahuje ani kliku ani nezávislou množinu velikosti $kl+1$. Opět přímo z definice ramseyovských čísel tak máme\[ r(kl+1,kl+1)>\left(r(k+1,k+1)-1\right)\left(r(l+1,l+1)-1\right),\] takže\[ r(kl+1,kl+1)-1\geq\left(r(k+1,k+1)-1\right)\left(r(l+1,l+1)-1\right).\] \end{proof} \begin{cor} \label{cor:dolni-odhad-r-2i-2i}Nechť $i\in\N_{0}$. Potom \[ r(2^{i}+1,2^{i}+1)\geq5^{i}+1.\] \end{cor} \begin{proof} Indukcí podle $i$. Pro $i=0$ máme $r(2,2)\geq2$, což platí, neboť víme, že obecně $r(k,2)=k$. Indukční krok $i-1\to i$ pro $i\geq1$: Zvolme $k=2^{i-1},l=2$. Potom použijeme předchozí větu a máme\[ r(2^{i}+1,2^{i}+1)-1=r(2^{i-1}\cdot2+1,2^{i-1}\cdot2+1)-1\geq\] \[ \geq\left(r(2^{i-1}+1,2^{i-1}+1)-1\right)\left(r(2+1,2+1)-1\right)\geq5^{i-1}\cdot5=5^{i}.\] V poslední nerovnosti jsme použili indukční předpoklad. \end{proof} \begin{rem} $r(k,k)$ je rostoucí funkce v $k$, což je zřejmé už z definice. Dále pro každé $k\in\N$ existuje $i\in\N_{0}$ tak, že\[ 2^{i}+1\leq k<2^{i+1}+1.\] Z pravé nerovnosti dostáváme\begin{equation} \frac{k-1}{2}\leq2^{i}.\label{eq:odhad-k-i}\end{equation} Můžeme tedy nejprve odhadnout\[ \left(2^{i}\right)^{\log_{2}5}=2^{i\log_{2}5}=5^{i}\leq r(2^{i}+1,2^{i}+1)\leq r(k,k)\] a nyní s využitím (\ref{eq:odhad-k-i}) dostaneme\[ O\left(k^{\log_{2}5}\right)=\left(\frac{k-1}{2}\right)^{\log_{2}5}\leq\left(2^{i}\right)^{\log_{2}5}\leq r(k,k).\] Máme tedy dolní odhad $r(k,k)$, který je nesrovnatelně menší než horní odhad odvozený v důsledku \ref{cor:horni-odhad-r-k-k}. Jedná se o nejlepší známou \emph{konstruktivní} mez. To znamená, že pro každé $n<\left(\frac{k-1}{2}\right)^{\log_{2}5}$ jsme schopni najít graf na $n$ vrcholech, který neobsahuje ani $K_{k}$ ani nezávislou množinu velikosti $k$. Ke konstrukci grafu již máme všechny znalosti: K danému $k$ nalezneme $i$, a dále podle důsledku \ref{cor:dolni-odhad-r-2i-2i} (indukcí podle $\tilde{i}=0,1,2,...,i$), pomocí kompozice popsané v důkazu věty \ref{thm:nerovnost-r-kl}, nalézáme postupně grafy na stále větším počtu vrcholů, které neobsahují kliku ani nezávislou množinu velikosti $2^{\tilde{i}}+1$. \end{rem} \subsection{Erdösova věta - dolní odhad $r(k,k)$} Než vyslovíme větu, která udává ještě lepší (avšak již nikoliv konstruktivní) dolní odhad $r(k,k)$, připravíme si malé technické lemma, které odhaduje kombinační číslo $\binom{n}{k}$. \begin{lem} \label{lem:odhad-n-nad-k}Nechť $n,k\in\N,n\geq k$. Potom\[ \binom{n}{k}\leq\left(\frac{n\e}{k}\right)^{k}.\] \end{lem} \begin{proof} Dokážeme dokonce silnější tvrzení\[ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{k}\leq\left(\frac{n\e}{k}\right)^{k}.\] Vezměme $x\in(0,1]$. Potom z binomické věty plyne\[ \sum_{i=1}^{k}\binom{n}{i}x^{i}\leq\sum_{i=1}^{n}\binom{n}{i}x^{i}=(1+x)^{n}.\] Nerovnost vynásobíme $x^{-k}$ a dostaneme\[ \sum_{i=1}^{k}\binom{n}{i}\underbrace{x^{i-k}}_{\geq1}\leq\frac{(1+x)^{n}}{x^{k}}.\] Protože pro každé $x\in\R$ platí (např. z Taylorova rozvoje) nerovnost $1+x\leq\e^{x}$, tak\[ \sum_{i=1}^{k}\binom{n}{i}\leq\sum_{i=1}^{k}\binom{n}{i}\underbrace{x^{i-k}}_{\geq1}\leq\frac{(1+x)^{n}}{x^{k}}\leq\frac{\e^{xn}}{x^{k}}.\] Z předpokladu platí $\frac{k}{n}\in(0,1]$, a tak je možné dosadit $x=\frac{k}{n}$, čímž dostaneme\[ \sum_{i=1}^{k}\binom{n}{i}\leq\frac{\e^{xn}}{x^{k}}=\frac{\e^{\frac{k}{n}n}}{\left(\frac{k}{n}\right)^{k}}=\left(\frac{n\e}{k}\right)^{k}.\] \end{proof} \begin{thm} \textbf{\emph{(Erdös)}} Nechť $k\in\N$. Potom platí\[ d\cdot k\cdot2^{\frac{k}{2}}\leq r(k,k),\] kde $d\in\R^{+}$. \end{thm} \begin{rem*} Erdösova věta udává nejlepší známou dolní mez pro $r(k,k)$. Tato mez je ve tvaru exponenciely o základu $2^{\frac{1}{2}}=\sqrt{2}$. Přitom horní mez je podle důsledku \ref{cor:horni-odhad-r-k-k} exponenciela o základu $4$. \end{rem*} \begin{proof} Nechť je dáno $k\in\N$. Spočítáme pravděpodobnost, že náhodný graf $G_{n}$ na $n$ vrcholech (viz. také věta \ref{thm:posloupnost-nahod-grafu}) obsahuje kliku nebo nezávislou množinu velikosti $k$. Pokud pro nějaké $n$ je tato pravděpodobnost menší než $1$, tj.\begin{equation} \Pr\left(\left(\omega(G_{n})\geq k\right)\vee\left(\alpha(G_{n})\geq k\right)\right)<1,\label{eq:pravd-mensi-nez-1}\end{equation} tak pravděpodobnost doplňkového jevu je nenulová, tj.\[ \Pr\left(\left(\omega(G_{n})<k\right)\wedge\left(\alpha(G_{n})<k\right)\right)>0.\] To ale znamená, že existuje graf na $n$ vrcholech, pro nějž $\left(\omega(G_{n})<k\right)\wedge\left(\alpha(G_{n})<k\right)$, takže\[ \boxed{r(k,k)>n.}\] Abychom tedy dokázali tvrzení věty, stačí najít $n$ ve tvaru $n=d\cdot k\cdot2^{\frac{k}{2}}$ a dokázat pro něj vztah (\ref{eq:pravd-mensi-nez-1}). To nyní postupně provedeme. Náhodný graf $G_{n}$ má mezi libovolnými dvěma vrcholy hranu s pravděpodobností $\frac{1}{2}$. Pravděpodobnost, že $G_{n}$ obsahuje kliku velikosti $k$ na konkrétních vrcholech $v_{1},...,v_{k}$, je tedy\[ \left(\frac{1}{2}\right)^{\binom{k}{2}}.\] V následujícím hned dvakrát využijeme vztah pro pravděpodobnost sjednocení jevů $A_{j}$ ($j\in\J)$, který zní\begin{equation} \Pr\left(\bigcup_{j\in\J}A_{j}\right)\leq\sum_{j\in\J}\Pr(A_{j}).\label{eq:sjednoceni-jevu}\end{equation} Nejprve s jeho pomocí odhadneme pravděpodobnost, že $G_{n}$ obsahuje kliku velikosti $k$ na libovolných $k$ vrcholech, tj. na libovolné $k$-prvkové podmnožině $M\subset V(G_{n})$:\[ \Pr\left(\omega(G_{n})\geq k\right)\leq\sum_{M\in\binom{V(G)}{k}}\left(\frac{1}{2}\right)^{\binom{k}{2}}=\binom{n}{k}\frac{1}{2^{\binom{k}{2}}}.\] Dále si uvědomíme, že stejnou úvahu lze (díky pravděpodobnosti existence každé hrany rovné $\frac{1}{2}$) provést i pro nezávislou množinu, a tedy\[ \Pr\left(\alpha(G_{n})\geq k\right)=\Pr\left(\omega(G_{n})\geq k\right).\] Proto opět podle (\ref{eq:sjednoceni-jevu}) platí\[ \Pr\left(\left(\omega(G_{n})\geq k\right)\vee\left(\alpha(G_{n})\geq k\right)\right)\leq2\binom{n}{k}\frac{1}{2^{\binom{k}{2}}}.\] Použijeme-li odhad $\binom{n}{k}$ z lemmatu \ref{lem:odhad-n-nad-k}, dostaneme\[ \Pr\left(\left(\omega(G_{n})\geq k\right)\vee\left(\alpha(G_{n})\geq k\right)\right)\leq2\binom{n}{k}\frac{1}{2^{\binom{k}{2}}}\leq2\left(\frac{n\e}{k}\right)^{k}\frac{1}{2^{\frac{k(k-1)}{2}}}=\] \[ =\left(\underbrace{\frac{\sqrt[k]{2}}{2^{-\frac{1}{2}}}}_{\leq2}\,\cdot\,\frac{\frac{n\e}{k}}{2^{\frac{k}{2}}}\right)^{k}\leq\left(2\e\frac{n}{k2^{\frac{k}{2}}}\right)^{k}<1,\] kde poslední nerovnost je splněna, pokud \[ n<\underbrace{\frac{1}{2\e}}_{d}\cdot k\cdot2^{\frac{k}{2}}.\] Tím je věta dokázána. \end{proof}