01ZTGA:Kapitola2 4: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(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
[ 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 | 15. 1. 2012 | 23:45 | ||
Řídící stránka | editovat | Definiční stránka dokumentu a vložených obrázků | Admin | 7. 9. 2015 | 13:51 | ||
Header | editovat | Hlavičkový soubor | Karel.brinda | 15. 1. 2012 | 12:34 | header.tex | |
Kapitola0 | editovat | Úvod | Karel.brinda | 15. 1. 2012 | 12:36 | cast0.tex | |
Kapitola1_1 | editovat | Základní pojmy | Karel.brinda | 15. 1. 2012 | 12:46 | cast1_kapitola1.tex | |
Kapitola1_2 | editovat | Souvislost | Karel.brinda | 15. 1. 2012 | 12:49 | cast1_kapitola2.tex | |
Kapitola1_3 | editovat | Bipartitní grafy | Karel.brinda | 15. 1. 2012 | 12:50 | cast1_kapitola3.tex | |
Kapitola1_4 | editovat | Stromy | Kubuondr | 5. 1. 2019 | 09:06 | cast1_kapitola4.tex | |
Kapitola1_5 | editovat | Hledání minimální kostry grafu | Karel.brinda | 15. 1. 2012 | 12:51 | cast1_kapitola5.tex | |
Kapitola1_6 | editovat | Jednotažky | Karel.brinda | 15. 1. 2012 | 12:53 | cast1_kapitola6.tex | |
Kapitola1_7 | editovat | Hamiltonovské kružnice a grafy | Karel.brinda | 15. 1. 2012 | 13:34 | cast1_kapitola7.tex | |
Kapitola1_8 | editovat | Párování v grafech | Karel.brinda | 15. 1. 2012 | 13:40 | cast1_kapitola8.tex | |
Kapitola1_9 | editovat | Toky v sítích | Karel.brinda | 15. 1. 2012 | 13:44 | cast1_kapitola9.tex | |
Kapitola1_10 | editovat | Hranové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:48 | cast1_kapitola10.tex | |
Kapitola1_11 | editovat | Vrcholové obarvení grafu | Karel.brinda | 15. 1. 2012 | 13:52 | cast1_kapitola11.tex | |
Kapitola1_12 | editovat | Planární grafy | Karel.brinda | 15. 1. 2012 | 13:56 | cast1_kapitola12.tex | |
Kapitola1_13 | editovat | Vlastní čísla adjacenční matice grafu | Karel.brinda | 15. 1. 2012 | 13:57 | cast1_kapitola13.tex | |
Kapitola2_1 | editovat | Brouwerova věta o pevném bodě | Karel.brinda | 15. 1. 2012 | 14:11 | cast2_kapitola1.tex | |
Kapitola2_2 | editovat | Pravděpodobnostní důkazy v teorii grafů | Karel.brinda | 15. 1. 2012 | 14:12 | cast2_kapitola2.tex | |
Kapitola2_3 | editovat | Extremální teorie grafů | Karel.brinda | 15. 1. 2012 | 14:16 | cast2_kapitola3.tex | |
Kapitola2_4 | editovat | Ramseyovská čísla | Karel.brinda | 15. 1. 2012 | 14:18 | cast2_kapitola4.tex | |
Kapitola3_1 | editovat | Obyčejné mocninné řady | Karel.brinda | 15. 1. 2012 | 14:22 | cast3_kapitola1.tex | |
Kapitola3_2 | editovat | Exponenciální generující funkce | Karel.brinda | 15. 1. 2012 | 14: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}