01ZTGA:Kapitola2 4: Porovnání verzí

Z WikiSkripta FJFI ČVUT v Praze
Přejít na: navigace, hledání
(Založena nová stránka: %\wikiskriptum{01ZTGA})
 
 
Řádka 1: Řádka 1:
 
%\wikiskriptum{01ZTGA}
 
%\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}

Aktuální verze z 15. 1. 2012, 14:18

PDF [ 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.
ZIPKompletní zdrojový kód včetně obrázků.

Součásti dokumentu 01ZTGA

součástakcepopisposlední editacesoubor
Hlavní dokument editovatHlavní stránka dokumentu 01ZTGAKarel.brinda 15. 1. 201223:45
Řídící stránka editovatDefiniční stránka dokumentu a vložených obrázkůAdmin 7. 9. 201513:51
Header editovatHlavičkový souborKarel.brinda 15. 1. 201212:34 header.tex
Kapitola0 editovatÚvodKarel.brinda 15. 1. 201212:36 cast0.tex
Kapitola1_1 editovatZákladní pojmyKarel.brinda 15. 1. 201212:46 cast1_kapitola1.tex
Kapitola1_2 editovatSouvislostKarel.brinda 15. 1. 201212:49 cast1_kapitola2.tex
Kapitola1_3 editovatBipartitní grafyKarel.brinda 15. 1. 201212:50 cast1_kapitola3.tex
Kapitola1_4 editovatStromyKubuondr 5. 1. 201909:06 cast1_kapitola4.tex
Kapitola1_5 editovatHledání minimální kostry grafuKarel.brinda 15. 1. 201212:51 cast1_kapitola5.tex
Kapitola1_6 editovatJednotažkyKarel.brinda 15. 1. 201212:53 cast1_kapitola6.tex
Kapitola1_7 editovatHamiltonovské kružnice a grafyKarel.brinda 15. 1. 201213:34 cast1_kapitola7.tex
Kapitola1_8 editovatPárování v grafechKarel.brinda 15. 1. 201213:40 cast1_kapitola8.tex
Kapitola1_9 editovatToky v sítíchKarel.brinda 15. 1. 201213:44 cast1_kapitola9.tex
Kapitola1_10 editovatHranové obarvení grafuKarel.brinda 15. 1. 201213:48 cast1_kapitola10.tex
Kapitola1_11 editovatVrcholové obarvení grafuKarel.brinda 15. 1. 201213:52 cast1_kapitola11.tex
Kapitola1_12 editovatPlanární grafyKarel.brinda 15. 1. 201213:56 cast1_kapitola12.tex
Kapitola1_13 editovatVlastní čísla adjacenční matice grafuKarel.brinda 15. 1. 201213:57 cast1_kapitola13.tex
Kapitola2_1 editovatBrouwerova věta o pevném boděKarel.brinda 15. 1. 201214:11 cast2_kapitola1.tex
Kapitola2_2 editovatPravděpodobnostní důkazy v teorii grafůKarel.brinda 15. 1. 201214:12 cast2_kapitola2.tex
Kapitola2_3 editovatExtremální teorie grafůKarel.brinda 15. 1. 201214:16 cast2_kapitola3.tex
Kapitola2_4 editovatRamseyovská číslaKarel.brinda 15. 1. 201214:18 cast2_kapitola4.tex
Kapitola3_1 editovatObyčejné mocninné řadyKarel.brinda 15. 1. 201214:22 cast3_kapitola1.tex
Kapitola3_2 editovatExponenciální generující funkceKarel.brinda 15. 1. 201214: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}