Součásti dokumentu 01ZTGA
Zdrojový kód
%\wikiskriptum{01ZTGA}
\section{Extremální teorie grafů}
Věty z extremální teorie grafů vyjadřují vztahy typu
\begin{itemize}
\item ,,jistý počet něčeho už vynucuje něco{}`` nebo
\item ,,kolik něčeho může být, aby platilo něco{}``
\end{itemize}
\subsection{Turánova věta}
\begin{thm}
\textbf{\emph{\label{thm:turan}(Turán, 1943)}}
Nechť $G=(V,E)$ je graf, který neobsahuje kliku velikosti $p$ (viz.
definice \ref{def:klika-nez-mnozina}) , tj. $K_{p}$ není podgrafem
$G$. Potom\begin{equation}
\# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\label{eq:turan}\end{equation}
\end{thm}
Důkazů Turánovy věty existuje řada, my postupně provedeme důkaz založený
na následujícím lemmatu:
\begin{lem}
Nechť $G$ je graf (na pevném počtu vrcholů) neobsahující $K_{p}$
s maximálním počtem hran. Potom v $G$ neexistuje trojice vrcholů
$u,v,w$ takových, že $\{ v,w\}\in E$ a přitom $\{ u,v\}\notin E,\{ u,w\}\notin E$.
\hfill{}
\begin{center}
%Title: turan_lemma.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 18:00:48 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.096 20.003 to 10.478 20.003
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}%
} [lB] at 10.835 19.884
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}%
} [lB] at 7.499 19.884
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}%
} [lB] at 9.167 20.360
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.286 20.955
}%
\linethickness=0pt
\putrectangle corners at 7.468 21.088 and 10.867 19.852
\endpicture}
\end{center}
\hfill{}~
\end{lem}
\begin{proof}
Nejprve proveďme pomocnou úvahu: Buď $G=(V,E)$ bez $K_{p}$, nechť
$x\in V$. Sestrojme graf \[
G'=\left(V\cup\{ x'\},E\cup\left\{ \left.\{ v,x'\}\right|v\in V\wedge\{ v,x\}\in E\right\} \right),\]
pro nějž $\forall v\in V$ platí $\{ x,v\}\in E(G')\Leftrightarrow\{ x',v\}\in E(G')$.
Vrcholy $x$ a $x'$ jsou tedy v $G'$ zcela rovnocenné. Protože $\{ x,x'\}\notin E(G')$,
tak $G'$ \underbar{nemůže obsahovat} $K_{p}$. V $K_{p}$ by totiž
musel být buď jen vrchol $x$, nebo jen vrchol $x'$, což je spor,
protože v tom případě by musela klika $K_{p}$ existovat už v $G$.
Nyní postupujme sporem. Nechť v $G$ existuje trojice vrcholů $u,v,w$
daných vlastností. Potom mohou nastat dvě možnosti:
\begin{enumerate}
\item $d_{G}(u)<d_{G}(v)$ nebo $d_{G}(u)<d_{G}(w)$ (nechť BÚNO $d_{G}(u)<d_{G}(v)$).
V tomto případě ke grafu $G$ přidáme právě popsaným způsobem vrchol
$v'$ a ubereme vrchol $u$ (i se všemi hranami, které do něj vedly).
Nově vytvořený graf neobsahuje $K_{p}$, ale přitom má o\[
d_{G}(v')-d_{G}(u)=d_{G}(v)-d_{G}(u)>0\]
hran více než $G$, což je spor s maximálním počtem hran grafu $G$.
\item $d_{G}(u)\geq d_{G}(v)$ a $d_{G}(u)\geq d_{G}(w)$. V tomto případě
ke $G$ přidáme kopie $u',u''$ a ubereme vrcholy $v,w$. Nový graf
opět neobsahuje $K_{p}$ a má o\[
2d_{G}(u)-d_{G}(v)-d_{G}(w)+1>0\]
hran více než $G$, což je spor. Jedničku přičítáme proto, že $\{ v,w\}\in E$,
a odečtením stupňů vrcholů $v,w$ jsme tuto hranu odečetli od celkového
počtu hran dvakrát.
\end{enumerate}
\end{proof}
\begin{cor*}
Relace $\oslash$ na množině vrcholů $V$ grafu $G$ s vlastnostmi
z minulého lemmatu definovaná jako\[
\left(u\oslash v\right)\Leftrightarrow\{ u,v\}\notin E\]
je ekvivalence na $V$.
\end{cor*}
\begin{proof}
Symetrie a reflexivita relace $\oslash$ jsou zřejmé. Tranzitivitu
pak vyjadřuje předchozí lemma:\[
\{ v,u\}\notin E\wedge\{ u,w\}\notin E\Rightarrow\{ v,w\}\notin E.\]
\end{proof}
Nyní přikročíme přímo k důkazu tvrzení Turánovy věty.
\begin{proof}
Mějme tedy $G=(V,E)$ bez $K_{p}$, s maximálním počtem hran. Bude-li
platit (\ref{eq:turan}) pro tento $G$, bude platit i pro libovolný
jiný graf bez $K_{p}$ (s nejvýše stejným počtem hran). $V$ je rozdělena
na třídy ekvivalence podle relace $\oslash$\[
V=V_{1}\cup V_{2}\cup...\cup V_{s},\]
přičemž z definice $\oslash$ platí:
\begin{itemize}
\item \begin{equation}
\left(\forall i\in\hat{s}\right)\left(\forall u,v\in V_{i}\right)\left(\{ u,v\}\notin E\right),\label{eq:turan-podm1}\end{equation}
\item \begin{equation}
\left(\forall i,j\in\hat{s},i\neq j\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:turan-podm2}\end{equation}
\end{itemize}
Mezi každými dvěma vrcholy z různých tříd tedy vedou hrany, ale v
jedné třídě není hrana mezi žádnými dvěma vrcholy.
Počet tříd je $s=p-1$. Kdyby jich totiž bylo alespoň $p$, bylo by
možné vybrat z každé z nich jeden vrchol, a vybraná podmnožina $V$
by tvořila kliku velikosti $s\geq p$, takže by v $G$ existovala
i $K_{p}\subset K_{s}\subset G$. Kdyby jich naopak bylo méně než
$p-1$, potom bychom mohli jednu třídu ekvivalence rozbít na dvě (přidat
hrany mezi odpovídajícími množinami vrcholů), a stále by graf neobsahoval
$K_{p}$ (je jasné, že různé vrcholy z $K_{p}$ musí ležet v různých
třídách $V_{i}$). To by ale byl spor s maximalitou počtu hran v $G$.
$V$ se tedy skládá z $p-1$ podmnožin $V_{1},...,V_{p-1}$ s vlastnostmi
(\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Označme si $k_{i}=\# V_{i}$
pro každé $i\in\widehat{p-1}$. Potom\[
n=\sum_{i=1}^{p-1}k_{i}.\]
Počet hran mezi $V_{i}$ a $V_{j}$ pro $i\neq j$ je zřejmě $k_{i}k_{j}$,
takže počet hran v celém grafu je\begin{equation}
\sum_{1\leq i<j\leq p-1}k_{i}k_{j}\label{eq:turan-pocet-hran}\end{equation}
a přitom v $G$ je počet hran maximální mezi všemi grafy na $n=\# V$
vrcholech, které neobsahují $K_{p}$. Je tedy maximální i mezi takovými
z nich, které mají stejný ,,tvar{}`` jako $G$: jejich množina vrcholů
je nějak rozdělena na $p-1$ neprázdných disjunktních podmnožin, které
splňují (\ref{eq:turan-podm1}) a (\ref{eq:turan-podm2}). Přitom
každý graf, který splňuje tyto podmínky, neobsahuje $K_{p}$. Každý
z těchto grafů je navíc jednoznačně (až na izomorfismus) určen $(p-1)$-ticí
$(k_{1},...,k_{p-1})$. Počet hran v $G$ je potom možno vyjádřit
jako\[
\max\left(\sum_{1\leq i<j\leq p-1}k_{i}k_{j}\right)\]
za podmínky\[
n=\sum_{i=1}^{p-1}k_{i}\,,\; k_{i}\in\N_{0}.\]
Maxima počtu hran se však nabyde právě tehdy, když počet ,,nehran{}``
(dvojic vrcholů, mezi nimiž nevede hrana) bude minimální. Ekvivalentně
tak lze hledat\[
\min\left(\sum_{i=1}^{p-1}\binom{k_{i}}{2}\right)\]
za stejných podmínek, což bude jednodušší. Protože chceme pouze shora
odhadnout skutečný počet hran v $G$, vyřešíme úlohu minima bez podmínky
na celočíselnost proměnných $k_{i}$. Hledáme tedy vázaný extrém funkce\[
f(x_{1},...,x_{p-1})=\sum_{i=1}^{p-1}\binom{x_{i}}{2}=\sum_{i=1}^{p-1}\frac{1}{2}x_{i}(x_{i}-1)\]
za podmínky\[
\sum_{i=1}^{p-1}x_{i}=n.\]
Sestavíme Lagrangeovu funkci\[
\Lambda(x_{1},...,x_{p-1})=f(x_{1},...,x_{p-1})-\lambda\left(\sum_{i=1}^{p-1}x_{i}-n\right)\]
a po zderivování a položení $\left(\forall i\in\widehat{p-1}\right)\left(\partial_{i}\Lambda=0\right)$
dostaneme\[
0=\frac{\partial\Lambda}{\partial x_{i}}=x_{i}-\frac{1}{2}-\lambda\;\Rightarrow x_{i}=\lambda+\frac{1}{2}.\]
Pokud dosadíme do podmínky vazby, vyjde $\lambda=\frac{n}{p-1}-\frac{1}{2}$,
takže pro všechna $x_{i}$ platí \[
x_{i}=\frac{n}{p-1}.\]
Lze snadno ověřit, že se skutečně jedná o minimum, výpočtem (tzv.
Hessovy) matice $\vec{H}=\left(\frac{\partial^{2}\Lambda}{\partial x_{i}\partial x_{j}}\right)$.
Platí $\vec{H}=\vec{I}$, což je zřejmě pozitivně definitní matice.
Dosadíme-li nyní za $x_{i}$ do $\sum_{1\leq i<j\leq p-1}x_{i}x_{j}$,
získáme horní odhad skutečného počtu hran (\ref{eq:turan-pocet-hran}).
Všechny sčítance v sumě jsou stejné a jejich počet je $\binom{p-1}{2}$,
takže horní odhad počtu hran vychází jako\[
\left(\frac{n}{p-1}\right)^{2}\binom{p-1}{2}=\frac{n^{2}}{(p-1)^{2}}\frac{(p-1)(p-2)}{2}=\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right),\]
což je přesně (\ref{eq:turan}).
\end{proof}
\begin{rem*}
Důkaz Turánovy věty také ukazuje, jak graf s co největším počtem hran,
a přitom bez $K_{p}$, zkonstruovat. Například graf neobsahující $K_{3}$
s maximálním počtem hran bude úplný bipartitní s množinou vrcholů
$V$ rozdělenou na podmnožiny s počty vrcholů $\left[\frac{n+1}{2}\right]$
a $\left[\frac{n}{2}\right]$.
\end{rem*}
V následujícím ukážeme jednu z aplikací Turánovy věty.
\begin{defn*}
Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$ je množina bodů v rovině.
\textbf{Průměrem} (diametrem) množiny $S$ rozumíme číslo\[
\mathrm{diam}\, S=\max_{i,j\in\hat{n}}\left\Vert x_{i}-x_{j}\right\Vert .\]
\end{defn*}
\begin{rem*}
Nechť $S=\{ x_{1},...,x_{n}\}\subset\R^{2}$, $\mathrm{diam}\, S\leq1$,
$d\in(0,1)$. Otázkou je, kolik párů bodů $x_{i},x_{j}$ má vzdálenost
$\geq d$, a jestli tento počet lze jiným uspořádáním bodů $x_{1},...,x_{n}$
zvýšit. Jako příklad si vezměme $n=6,d=\frac{\sqrt{3}}{2}-\varepsilon$,
$\varepsilon>0$. Potom existuje $\binom{6}{2}=15$ různých párů.
Na obrázku \ref{cap:vzdalene-pary} jsou páry od sebe vzdálených bodů
spojeny čarami. Vlevo má $9$ párů vzdálenost $\geq d$ a $6$ párů
vzdálenost $<d$, vpravo má $12$ párů vzdálenost $\geq d$ a jen
$3$ páry vzdálenost $<d$. Obecně omezuje počet vzdálených párů následující
věta. %
\begin{figure}
\begin{center}
%Title: diameter1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:47:04 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 15.001 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.311 17.264
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 16.669 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 14.525 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 13.216 17.264
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.857 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 11.191 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 16.669
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.905:1.905 360 degrees
from 11.430 18.574 center at 9.525 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\putrule from 13.214 17.266 to 16.311 17.266
\plot 16.311 17.266 15.001 20.479 /
\plot 15.001 20.479 12.859 17.621 /
\putrule from 12.859 17.621 to 16.669 17.621
\plot 16.669 17.621 14.525 20.479 /
\plot 14.525 20.479 13.214 17.266 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\plot 14.525 20.479 12.859 17.621 /
\plot 12.859 17.621 16.311 17.266 /
\plot 16.311 17.266 14.525 20.479 /
}%
%
% Fig POLYLINE object
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{1,0,0}\plot 15.001 20.479 13.214 17.266 /
\plot 13.214 17.266 16.669 17.621 /
\plot 16.669 17.621 15.001 20.479 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\putrule from 9.525 20.479 to 9.525 16.669
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\plot 7.857 17.621 11.191 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\putrule from 7.857 19.526 to 11.191 19.526
\plot 11.191 19.526 9.525 16.669 /
\plot 9.525 16.669 7.857 19.526 /
\plot 7.857 19.526 11.191 17.621 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{1,0,0}\putrule from 7.857 17.621 to 11.191 17.621
\plot 11.191 17.621 9.525 20.479 /
\plot 9.525 20.479 7.857 17.621 /
}%
\linethickness=0pt
\putrectangle corners at 7.603 20.612 and 16.804 16.535
\endpicture}
\end{center}
\caption{\label{cap:vzdalene-pary}Páry vzdálených bodů v rovině}
\end{figure}
\end{rem*}
\begin{thm}
\label{thm:vzdalene-pary}Nechť $d\in\left(\frac{1}{\sqrt{2}},1\right)$.
Potom počet párů z $n$-prvkové množiny $S\subset\R^{2}$ s průměrem
$\mathrm{diam}\, S\leq1$, které mají vzdálenost alespoň $d$, je
nejvýše $\left[\frac{n^{2}}{3}\right]$. Přitom tohoto počtu lze vhodným
uspořádáním bodů vždy dosáhnout.
\end{thm}
Než dokážeme tuto větu, která je snadným důsledkem Turánovy věty,
připravíme si ješte malé lemma.
\begin{lem}
Z libovolných čtyř bodů v rovině lze vybrat tři tak, že tvoří pravoúhlý
nebo tupoúhlý trojúhelník (přitom přímku považujeme za tupoúhlý trojúhelník
s úhlem $180^{\circ}$).
\end{lem}
\begin{proof}
Mohou nastat dva případy:
\begin{enumerate}
\item Jeden bod $x$ leží v konvexním obalu zbylých tří bodů $y_{1},y_{2},y_{3}$.
Potom součet vrcholových úhlů $\measuredangle y_{1}xy_{2}$,$\measuredangle y_{2}xy_{3}$,$\measuredangle y_{3}xy_{1}$
je $360^{\circ}$, takže jeden z nich musí být dokonce $\geq120^{\circ}$.
\item Všechny čtyři body tvoří konvexní čtyřúhelník. Protože v něm je součet
úhlů $360^{\circ}$, musí tam existovat jeden $\geq90^{\circ}$.
\end{enumerate}
\end{proof}
\begin{proof}
(věty \ref{thm:vzdalene-pary})
Definujme graf $G=(S,E)$, kde $\{ x_{i},x_{j}\}\in E\Leftrightarrow\left\Vert x_{i}-x_{j}\right\Vert \geq d$.
Potom $G$ neobsahuje kliku $K_{4}$. Jestliže totiž čtyři body (vrcholy
$G$) tvoří $K_{4}$, tak jsou každé dva z nich od sebe dál než $d$.
Podle předchozího lemmatu lze vybrat tři, které tvoří tupoúhlý trojúhelník.
Obě ,,odvěsny{}`` tohoto trojúhelníka jsou delší než $d\geq\frac{1}{\sqrt{2}}$,
a tak je ,,přepona{}`` delší než $1$, což je spor.
Podle Turánovy věty pro $p=4$ potom platí\[
\# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)=\frac{n^{2}}{3}.\]
Nyní zbývá dokázat, že této mezi se lze přiblížit. Za tím účelem se
podívejme na důkaz Turánovy věty. Počtu hran $\frac{n^{2}}{3}$ se
dosahuje, jestliže graf $G$ je rozdělen do $p-1=3$ ,,knedlíků{}``,
v nichž nevedou hrany (body z jednoho ,,knedlíku{}`` jsou v rovině
blízko sebe) a mezi nimiž naopak vedou všechny hrany (celé ,,knedlíky{}``
jsou v rovině daleko od sebe), a jestliže počet vrcholů v každém ,,knedlíku{}``
je $\frac{n}{p-1}=\frac{n}{3}$. Protože to však nemusí být celé číslo,
lze ve skutečnosti dosáhnout počtu hran jen $\left[\frac{n^{2}}{3}\right]$.
Dodejme, že popsané uspořádání přesně odpovídá pravé části obrázku
\ref{cap:vzdalene-pary}.
\end{proof}
\subsection{Erdösova věta}
\begin{lem*}
\textbf{\emph{\label{lem:jensenova-nerovnost}(Jensenova nerovnost)}}
Nechť $f:[a,b]\mapsto\R$ je konvexní funkce, tj.\[
\left(\forall x_{1},x_{2}\in[a,b]\right)\left(\forall\lambda\in[0,1]\right)\left(\lambda f(x_{1})+(1-\lambda)f(x_{2})\geq f(\lambda x_{1}+(1-\lambda)x_{2}\right).\]
Nechť $\alpha_{i}\in\R_{0}^{+}$ pro každé $i\in\hat{n}$, $\sum_{i=1}^{n}\alpha_{i}=1$
a nechť $x_{i}\in[a,b]$ pro každé $i\in\hat{n}$. Potom\[
\sum_{i=1}^{n}\alpha_{i}f(x_{i})\geq f\left(\sum_{i=1}^{n}\alpha_{i}x_{i}\right).\]
\end{lem*}
\begin{proof}
Snadno se ukáže indukcí podle $n$, byl proveden například v \cite{TIN}.
\end{proof}
\begin{cor*}
Za stejných předpokladů platí i\begin{equation}
\frac{1}{n}\sum_{i=1}^{n}f(x_{i})\geq f\left(\frac{1}{n}\sum_{i=1}^{n}x_{i}\right).\label{eq:konvexni-fce}\end{equation}
\end{cor*}
\begin{proof}
Položíme $\alpha_{i}=\frac{1}{n}$ pro každé $i\in\hat{n}$.
\end{proof}
\begin{thm}
\textbf{\emph{(Erdös)}}
Nechť $G=(V,E)$ je graf, který neobsahuje jako svůj podgraf $K_{r,r}$
(úplný bipartitní graf na $r+r$ vrcholech). Potom\[
\# E\leq C_{r}\cdot n^{2-\frac{1}{r}},\]
kde $C_{r}$ je konstanta nezávislá na $n=\# V$.
\end{thm}
\begin{rem*}
Vždy platí $\# E\leq\binom{n}{2}\leq\frac{n^{2}}{2}$. Turánova věta
omezuje počet hran grafu bez $K_{p}$ podle vztahu (\ref{eq:turan}),
tj. řádově stejně. Erdösova věta však udává řádově \emph{menší} omezení.
\end{rem*}
\begin{proof}
Nechť $G=(V,E)$, kde BÚNO $V=\hat{n}$, je graf bez $K_{r,r}$. Vytvoříme
nový bipartitní graf $G'$, který bude definován na základě grafu
$G$ jako $G'=(V_{1}\cup V_{2},E')$, kde $V_{1}=V$ a $V_{2}=\binom{V}{r}$
je množina všech $r$-prvkových podmnožin $V$. Přitom \[
\{\underbrace{i}_{\in V_{1}},\underbrace{\{ k_{1},...,k_{r}\}}_{\in V_{2}}\}\in E',\]
právě když $\{ k_{1},...,k_{r}\}\subset N(i)$ v grafu $G$, tj,
právě když $\left(\forall j\in\hat{r}\right)\left(\{ i,k_{j}\}\in E\right)$.
Základem odvození požadované nerovnosti bude vyjádření počtu hran
v grafu $G'$ dvěma různými způsoby, a to jednak jako počet hran vycházejících
z $V_{1}$, a jednak jako \emph{odhad} počtu hran vycházejících z
$V_{2}$:
\begin{enumerate}
\item Z definice $E'$ plyne, že z $i\in V_{1}$ vede v $G'$ tolik hran,
kolik je $r$-prvkových podmnožin množiny sousedů vrcholu $i$:\[
d_{G'}(i)=\binom{d_{G}(i)}{r}.\]
Přitom pokud $d_{G}(i)=\# N_{G}(i)<r$, pak $d_{G'}(i)=0$, což je
v souladu s definicí kombinačního čísla. Počet všech hran v $G'$
je tedy\[
\sum_{i=1}^{n}\binom{d_{G}(i)}{r}.\]
\item Platí $d_{G'}(\{ k_{1},...,k_{r}\})\leq r-1$. V opačném případě by
totiž z definice $E'$ existovalo (alespoň) $r$ vrcholů $l_{1},...,l_{r}$
v grafu $G$ různých od $k_{1},...,k_{r}$, které by byly napojeny
na všechny vrcholy $k_{1},...,k_{r}$. To by ale znamenalo, že $G$
obsahuje $K_{r,r}$. Různost vrcholů, tj. skutečnost, že\[
\left(\forall j\in\hat{r}\right)\left(l_{j}\notin\{ k_{1},...,k_{r}\}\right)\]
plyne z toho, že žádný vrchol v $G$ není v hraně sám se sebou. Proto
žádný $k_{j}\in V_{1}$ nemůže být v grafu $G'$ spojen hranou s vrcholem
$\{ k_{1},...,k_{r}\}\in V_{2}$. Z uvedené úvahy plyne, že počet
hran v $G'$ musí být menší nebo roven než\[
(r-1)\underbrace{\binom{n}{r}}_{\# V_{2}}.\]
\end{enumerate}
Srovnáním obou vyjádření dostáváme nerovnost\begin{equation}
\sum_{i=1}^{n}\binom{d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\label{eq:erdos-nerovnost1}\end{equation}
kterou již budeme jen dále odhadovat a upravovat do požadovaného tvaru.
Pokud \[
\frac{1}{n}\underbrace{\sum_{i=1}^{n}d_{G}(i)}_{2\# E}\leq r-1,\]
tak potom \[
\# E\leq\frac{1}{2}(r-1)n\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\]
a není co dokazovat. Předpokládejme proto \begin{equation}
\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\geq r.\label{eq:erdos-predp}\end{equation}
Definujme konvexní funkci\[
f(x)=\begin{cases}
\binom{x}{r} & x\geq r\\
0 & x<r\end{cases},\]
kde dodefinování nulou je potřebné jen pro $x$ neceločíselné. Potom
$f\left(d_{G}(i)\right)=\binom{d_{G}(i)}{r}$ a podle (\ref{eq:konvexni-fce})
platí\[
n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}=n\cdot f\left(\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)\right)\leq\sum_{i=1}^{n}f(d_{G}(i))=\sum_{i=1}^{n}\binom{d_{G}(i)}{r},\]
přičemž levá strana je nenulová, takže ji lze použít k dalším odhadům
(proto je důležitý předpoklad \ref{eq:erdos-predp}). Použijeme-li
tento odhad v (\ref{eq:erdos-nerovnost1}), dostaneme\[
n\cdot\binom{\frac{1}{n}\sum_{i=1}^{n}d_{G}(i)}{r}\leq(r-1)\binom{n}{r},\]
neboli při označení $m=\# E$\begin{equation}
n\cdot\binom{2m/n}{r}\leq(r-1)\binom{n}{r}.\label{eq:erdos-nerovnost2}\end{equation}
Kombinační číslo $\binom{n}{k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$
lze odhadnout zdola a shora\[
\frac{(n-k+1)^{k}}{k!}\leq\binom{n}{k}\leq\frac{n^{k}}{k!},\]
což pro náš případ znamená\[
n\frac{\left(\frac{2m}{n}-r+1\right)^{r}}{r!}\leq n\binom{2m/n}{r}\leq(r-1)\binom{n}{r}\leq(r-1)\frac{n^{r}}{r!}.\]
Vynásobíme $\frac{r!}{n}$ a odmocníme $\sqrt[r]{...}$, takže dostaneme\[
\frac{2m}{n}-r+1\leq\sqrt[r]{r-1}n^{1-\frac{1}{r}}\]
a už jen upravujeme:\[
m\leq\frac{n}{2}\left(\sqrt[r]{r-1}n^{1-\frac{1}{r}}+r-1\right)=\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n\leq\frac{1}{2}\sqrt[r]{r-1}n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\]
\[
\leq\frac{1}{2}(r-1)n^{2-\frac{1}{r}}+\frac{1}{2}(r-1)n^{2-\frac{1}{r}}\leq\underbrace{(r-1)}_{C_{r}}n^{2-\frac{1}{r}}\]
\end{proof}
\begin{rem*}
Pro $r=2$, tj. pro graf bez $K_{2,2}=C_{4}$ máme odhad\[
\# E\leq C_{r}\cdot n^{3/2}.\]
Nerovnost (\ref{eq:erdos-nerovnost2}) lze však v tomto případě upravovat
šikovněji, a tak získat (trochu) přísnější odhad:\begin{eqnarray*}
n\frac{\frac{1}{n}2m\left(\frac{1}{n}2m-1\right)}{2} & \leq & \frac{n(n-1)}{2}\\
2m(2m-n) & \leq & n^{3}-n^{2}\\
4m^{2}-2nm-n^{3}+n^{2} & \leq & 0\end{eqnarray*}
Kvadratickou rovnici pro počet hran $m$ vyřešíme:\[
m_{1,2}=\frac{2n\pm\sqrt{4n^{2}-16(-n^{3}+n^{2})}}{8}=\frac{n\pm n\sqrt{4n-3}}{4}.\]
Jeden kořen je záporný, takže nehraje roli. Dostáváme tedy odhad\begin{equation}
\# E\leq\frac{n+n\sqrt{4n-3}}{4}=\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\label{eq:odhad-E-bez-K22}\end{equation}
V následujícím ukážeme, jak se mu lze vhodnou konstrukcí grafu přiblížit.
\end{rem*}
\subsection{Graf s $\# E$ blízkým Erdösovu odhadu}
Zkonstruujeme graf $G=(V,E)$ neobsahující $K_{2,2}=C_{4}$ s počtem
hran blížícím se odhadu (\ref{eq:odhad-E-bez-K22}). V následujícím
velmi pěkném postupu se využije mnoho znalostí z různých partií matematiky.
Nechť $p$ je prvočíslo. Uvažujme těleso zbytkových tříd $\Z_{p}=\{0,1,2,...,p-1\}$
a vektorový prostor $\Z_{p}^{3}$ nad tělesem $\Z_{p}$. Vrcholy grafu
$G$ budou představovat přímky v $\Z_{p}^{3}$ procházející počátkem.
V tomto prostoru má každá taková přímka právě $p$ bodů, protože ji
lze vyjádřit jako lineární obal jejího směrového vektoru, který je
z definice roven\[
[\underbrace{(x_{1},x_{2},x_{3})}_{\vec{x}}]_{\lambda}=\left\{ \left.(kx_{1},kx_{2},kx_{3})\right|k\in\Z_{p}\right\} .\]
Různých nenulových vektorů v $\Z_{p}^{3}$ je zřejmě $p^{3}-1$. Protože
každá přímka má $p$ bodů, z nichž $p-1$ jsou nenulové vektory, je
možné ji reprezentovat libovolným z $p-1$ směrových vektorů. Proto
počet všech přímek procházejících počátkem je roven\[
\# V=\frac{p^{3}-1}{p-1}=p^{2}+p+1.\]
Označme si (vybrané) směrové vektory přímek ( = vrcholů grafu $G$)
$v_{1},v_{2},...,v_{p^{2}+p+1}$ po řadě jako $\vec{x}_{1},...,\vec{x}_{p^{2}+p+1}$,
tj. nechť platí\[
\left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(v_{i}=[\vec{x}_{i}]_{\lambda}\right).\]
Dále definujme ,,pseudoskalární{}`` součin vektorů $\vec{x}=(x_{1},x_{2},x_{3})$
a $\vec{y}=(y_{1},y_{2},y_{3})$ z prostoru $\Z_{p}^{3}$ jako\[
\left\langle \vec{x},\vec{y}\right\rangle =x_{1}y_{1}+x_{2}y_{2}+x_{3}y_{3}.\]
Řekneme, že vektor $\vec{x}$ je kolmý na vektor $\vec{y}$, jestliže
$\left\langle \vec{x},\vec{y}\right\rangle =0$. Protože existují
vektory, které jsou kolmé samy na sebe, nejedná se o pravý skalární
součin. Nyní množinu hran $E$ definujeme jako\[
E=\left\{ \left.\{ v_{i},v_{j}\}\right|i\neq j\wedge\left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\right\} .\]
\begin{example*}
Abychom si dobře uvědomili, jak je graf $G$ definován, ukážeme si
jej pro $p=2$. Na obrázku \ref{cap:konstrukce-Z2} jsou jednotlivé
vrcholy grafu označeny svými směrovými vektory. Je vidět, že například
vektor $(1,1,0)$ je kolmý sám na sebe.%
\begin{figure}
\begin{center}
%Title: konstrukce_Z2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:35:44 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 12.859 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.715 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 17.621
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.572 19.526
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 8.572 19.526 to 8.572 20.973
\putrule from 8.572 20.955 to 12.876 20.955
\putrule from 12.859 20.955 to 12.859 17.621
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 8.572 20.955 10.715 20.003 /
\putrule from 10.715 20.003 to 10.715 18.574
\plot 10.715 18.574 12.859 17.621 /
\putrule from 12.859 17.621 to 8.555 17.621
\putrule from 8.572 17.621 to 8.572 19.526
\plot 8.572 19.526 10.715 20.003 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,1)$}%
} [lB] at 13.214 17.503
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,1)$}%
} [lB] at 9.167 18.455
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,0,1)$}%
} [lB] at 7.023 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,0)$}%
} [lB] at 11.070 19.884
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(0,1,1)$}%
} [lB] at 13.214 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,0,0)$}%
} [lB] at 7.023 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$(1,1,0)$}%
} [lB] at 7.023 17.503
\linethickness=0pt
\putrectangle corners at 6.991 21.207 and 13.246 17.344
\endpicture}
\end{center}
\caption{\label{cap:konstrukce-Z2}Konstrukce $G$ pro $p=2$}
\end{figure}
\end{example*}
Ukážeme, že pro libovolné prvočíslo $p$ takto definovaný graf $G$
neobsahuje $K_{2,2}=C_{4}$. Kdyby $G$ obsahoval $C_{4}$, existovaly
by v něm vrcholy $v_{i},v_{j}$ spojené hranami s dalšími dvěma vrcholy
takto:
\hfill{}
\begin{center}
%Title: konstrukce_kolmost.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:16:56 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 7.620 20.479
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 9.049 20.955 7.620 20.479 /
\plot 7.620 20.479 9.049 20.003 /
\plot 9.049 20.003 10.478 20.479 /
\plot 10.478 20.479 9.049 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{j}$}%
} [lB] at 10.952 20.360
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{i}$}%
} [lB] at 6.905 20.360
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.003
}%
\linethickness=0pt
\putrectangle corners at 6.873 21.088 and 10.983 19.869
\endpicture}
\end{center}
\hfill{}~
\noindent Podívejme se však, kolik vrcholů může být hranami napojeno
na $v_{i}$ i na $v_{j}$. Označme $\vec{x}_{i}=(\alpha_{1},\alpha_{2},\alpha_{3})$,
$\vec{x}_{j}=(\beta_{1},\beta_{2},\beta_{3})$ a hledejme $\vec{y}=(\gamma_{1},\gamma_{2},\gamma_{3})$
kolmý na $\vec{x}_{i}$ i na $\vec{x}_{j}$. Pro $\vec{y}$ musí platit\begin{eqnarray*}
0=\left\langle \vec{x}_{i},\vec{y}\right\rangle & = & \alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3}\\
0=\left\langle \vec{x}_{j},\vec{y}\right\rangle & = & \beta_{1}\gamma_{1}+\beta_{2}\gamma_{2}+\beta_{3}\gamma_{3},\end{eqnarray*}
což znamená, že $\gamma_{1},\gamma_{2},\gamma_{3}$ jsou řešením homogenní
soustavy lineárních rovnic s maticí\[
\left(\begin{array}{ccc}
\alpha_{1} & \alpha_{2} & \alpha_{3}\\
\beta_{1} & \beta_{2} & \beta_{3}\end{array}\right).\]
Protože $\vec{x}_{i},\vec{x}_{j}$ jsou směrové vektory různých přímek,
jsou lineárně nezávislé, a tato matice má tedy hodnost $2$. Podle
Frobeniovy věty o řešení soustav lineárních rovnic pak existuje jediné
lineárně nezávislé řešení $\vec{y}$ této soustavy. Existuje tedy
jediná přímka se směrovým vektorem $\vec{y}$, která je kolmá na obě
přímky $v_{i},v_{j}$, neboli tato přímka jako vrchol grafu $G$ je
jediná, která je hranami spojena s $v_{i}$ i s $v_{j}$. Proto $G$
neobsahuje $C_{4}$.
Nyní postupně vyčíslíme počet hran v grafu $G$. Hledejme stupeň $d_{G}(v_{i})$
nějakého pevného vrcholu $v_{i}\in V$, neboli počet různých přímek,
které jsou kolmé na $v_{i}$. Ten je roven počtu \emph{různých} vektorů
$\vec{y}$ kolmých na $\vec{x}_{i}$, přičemž dva takové vektory jsou
\emph{různé}, když jsou lineárně nezávislé (to ovšem neznamená, že
všechny tyto vektory mají tvořit LN soubor). Použijeme-li již zavedené
značení pro $\vec{x}_{i}$ a $\vec{y}$, musí $\vec{y}$ splňovat
rovnici\[
0=\left\langle \vec{x}_{i},\vec{y}\right\rangle =\alpha_{1}\gamma_{1}+\alpha_{2}\gamma_{2}+\alpha_{3}\gamma_{3},\]
která má $2$ LN řešení $\vec{y}_{1},\vec{y}_{2}$. Počet všech řešení
této soustavy je $p^{2}$, protože jsou to právě vektory\[
\vec{y}=k_{1}\vec{y}_{1}+k_{2}\vec{y}_{2}\ ,\; k_{1},k_{2}\in\Z_{p}.\]
Máme tedy $p^{2}-1$ nenulových řešení, ale vždy $p-1$ z nich je
kolineárních, tj. jedná se o směrové vektory téže přímky. \underbar{Počet
různých přímek kolmých na $v_{i}$}, tj. počet \emph{různých} vektorů
$\vec{y}$ kolmých na $\vec{x}_{i}$, je tedy\[
\frac{p^{2}-1}{p-1}=p+1.\]
Tento výsledek si pro pozdější použití dobře zapamatujme. Nejedná
se totiž ještě o $d_{G}(v_{i})$, protože záleží na tom, zda $\vec{x}_{i}$
je kolmý sám na sebe. Zatím tedy můžeme shrnout:\[
\left(\forall i\in\{1,...,p^{2}+p+1\}\right)\left(d_{G}(v_{i})=\begin{cases}
p+1 & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle \neq0\\
p & \left\langle \vec{x}_{i},\vec{x}_{i}\right\rangle =0\end{cases}\right).\]
Dalším naším úkolem je zjistit, v kolika případech je $\vec{x}_{i}$
kolmý sám na sebe. Jestliže to dokážeme, bude už snadné vyjádřit celkový
počet hran grafu $G$. Definujme čtvercovou matici $\vec{A}$ řádu
$p^{2}+p+1$, jejíž prvky mají hodnotu\[
\vec{A}_{ij}=\begin{cases}
1 & \left\langle \vec{x}_{i},\vec{x}_{j}\right\rangle =0\\
0 & \textrm{jinak}.\end{cases}\]
Potom $\vec{A}_{ii}=1$, právě když $\vec{x}_{i}$ je kolmý sám na
sebe. Hledaný počet přímek kolmých na sebe sama je tedy roven počtu
nenulových prvků na diagonále matice $\vec{A}$, neboli její stopě
$\Tr\vec{A}$. Protože náš pseudoskalární součin je symetrický, je
i matice $\vec{A}$ symetrická, a tedy diagonalizovatelná. Podobnostní
transformace zachovává stopu, a proto $\Tr\vec{A}$ je rovna součtu
vlastních čísel $\vec{A}$.
$\vec{A}$ nemá zrovna jednoduchý tvar. Pro určení vlastních čísel
proto sestavíme $\vec{A}^{2}$, která vypadá mnohem lépe. Z definice
maticového násobení máme\[
\vec{A}_{ij}^{2}=\sum_{k=1}^{p^{2}+p+1}\vec{A}_{ik}\vec{A}_{kj},\]
což znamená, že\[
\vec{A}_{ij}^{2}=\#\left\{ \left.k\right|\left\langle \vec{x}_{k},\vec{x}_{i}\right\rangle =0\wedge\left\langle \vec{x}_{k},\vec{x}_{j}\right\rangle =0\right\} ,\]
tj. $\vec{A}_{ij}^{2}$ je počet přímek kolmých na $v_{i}$ i $v_{j}$.
My už ale víme, že pro $i\neq j$ je taková přímka právě jedna a pro
$i=j$ je těchto přímek $p+1$. Proto\[
\vec{A}^{2}=\left(\begin{array}{cccc}
p+1 & 1 & \cdots & 1\\
1 & p+1 & \cdots & 1\\
\vdots & \vdots & \ddots & \vdots\\
1 & 1 & \cdots & p+1\end{array}\right)=p\vec{I}+\vec{J},\]
kde $\vec{J}_{ij}=1$ pro každé $i,j$. Vlastní čísla matice $\vec{A}$
jsou posunuta o $p$ vzhledem k vlastním číslům matice $\vec{J}$:\[
\left(\vec{J}\vec{x}=\lambda\vec{x}\right)\Leftrightarrow\left(\vec{A}^{2}\vec{x}=(p\vec{I}+\vec{J})\vec{x}=(p+\lambda)\vec{x}\right)\]
Protože $\vec{J}$ má zřejmě hodnost $1$, má $\vec{J}$ jediné nenulové
vlastní číslo $\lambda$ a pak vlastní číslo $0$ s násobností (řád
matice$-1$), tj. $p^{2}+p$. Nenulové vlastní číslo $\vec{J}$ je
rovno řádu matice, tj. $\lambda=p^{2}+p+1$, protože\[
\vec{J}\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right)=\left(\begin{array}{c}
p^{2}+p+1\\
p^{2}+p+1\\
\vdots\\
p^{2}+p+1\end{array}\right)=(p^{2}+p+1)\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right).\]
Matice $\vec{A}^{2}$ má tedy vlastní číslo $(p^{2}+p+1)+p=(p+1)^{2}$
s násobností $1$ a vlastní číslo $0+p=p$ s násobností $p^{2}+p$.
Matice $\vec{A}$ má vlastní čísla rovná odmocninám z vlastních čísel
$\vec{A}^{2}$, tj.
\begin{itemize}
\item $p+1$ s násobností $1$
\item $\sqrt{p}$ s násobností $r$
\item $-\sqrt{p}$ s násobností $s$
\end{itemize}
\begin{rem*}
Vlastní číslo $p+1$ jsme mohli u matice zjistit rovnou podle\[
\vec{A}\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right)=\left(\begin{array}{c}
p+1\\
p+1\\
\vdots\\
p+1\end{array}\right)=(p+1)\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right),\]
protože počet jedniček v každém ($i$-tém) řádku $\vec{A}$, což je
počet přímek kolmých na $v_{i}$, je roven $p+1$.
\end{rem*}
Když nyní známe vlastní čísla $\vec{A}$, můžeme konečne vyjádřit\[
\Tr\vec{A}=(p+1)+(r-s)\sqrt{p},\]
a protože stopa celočíselné matice nemůže být neceločíselná (přitom
$p$ je prvočíslo, takže $\sqrt{p}\notin\N)$, musí nutně $r=s$ a
tedy\[
\Tr\vec{A}=p+1.\]
Nyní tedy víme, že počet vrcholů $G$ se stupněm $p$ je $p+1$. Ostatních
$p^{2}$ vrcholů má stupeň $p+1$. Proto již lze určit počet hran
v grafu $G$:\[
2\# E=\sum_{v\in V}d_{G}(v)=(p+1)p+p^{2}(p+1)=p(p+1)^{2},\]
\[
\# E=\frac{p(p+1)^{2}}{2}.\]
Abychom mohli $\# E$ srovnat s (\ref{eq:odhad-E-bez-K22}), musíme
jej vyjádřit pomocí $n=\# V$. Z rovnosti \begin{equation}
n=p^{2}+p+1\label{eq:konstrukce-pocet-vrcholu}\end{equation}
tedy získáme\[
p=\frac{-1+\sqrt{4n-3}}{2}\]
a po vhodné úpravě, která umožní dosadit za $p^{2}+p$ z (\ref{eq:konstrukce-pocet-vrcholu}),
dostaneme\[
\# E=\frac{p(p+1)^{2}}{2}=\frac{p+1}{2}(p^{2}+p)=\frac{1+\sqrt{4n-3}}{4}(n-1)=\frac{1}{4}(n-1)\left(1+\sqrt{4n-3}\right).\]
Přitom z Erdösovy věty máme odhad\[
\# E\leq\frac{1}{4}n\left(1+\sqrt{4n-3}\right).\]
Je tedy vidět, že pro $n=p^{2}+p+1$, kde $p$ je prvočíslo, je tento
odhad docela těsný.
\subsection{Počet $K_{3}$ a $\bar{K}_{3}$ v grafu}
\begin{thm}
Nechť $G=(V,E)$ je graf na $n$ vrcholech. Potom počet klik $K_{3}$
a podgrafů $\bar{K}_{3}$ v grafu $G$ je alespoň \[
\frac{n(n-1)(n-5)}{24}.\]
\end{thm}
\begin{proof}
Tři vrcholy z $n$ vrcholů lze vybrat $\binom{n}{3}$ způsoby. Až
na izomorfismus existují pouze $4$ podgrafy (tj. $4$ \emph{typy}
podgrafů), které mohou být indukované těmito třemi vrcholy. Jestliže
obrázkem podgrafu umístěným do kroužku rozumíme počet podgrafů tohoto
typu v grafu $G$, můžeme zapsat následující rovnici:
\hfill{}
\begin{center}
%Title: K3_rovnice1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:48:56 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 ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 15.953 18.754 center at 15.418 18.754
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.716 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.121 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.420 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.811 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 13.513 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 14.110 18.574
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 14.347 18.754 center at 13.811 18.754
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 12.738 18.754 center at 12.203 18.754
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 11.132 18.754 center at 10.596 18.754
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 15.716 18.574 to 15.119 18.574
\plot 15.119 18.574 15.418 19.111 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 13.513 18.574 to 14.108 18.574
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 /
\plot 10.596 19.111 10.892 18.574 /
\putrule from 10.892 18.574 to 10.298 18.574
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}$}%
} [lB] at 16.133 18.633
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 14.465 18.633
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 11.250 18.633
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 12.859 18.633
\linethickness=0pt
\putrectangle corners at 10.029 19.321 and 16.165 18.186
\endpicture}
\end{center}
\hfill{}~
\noindent Vezměme nyní vrchol $v\in V$. Z něj vede hrana do $d_{G}(v)$
vrcholů a do dalších $n-1-d_{G}(v)$ z něj hrana nevede. Počet \emph{uspořádaných}
trojic $(v,u,w)$ takových, že $\{ v,u\}\in E$ a zároveň $\{ v,w\}\notin E$,
je tedy\[
\sum_{v\in V}d_{G}(v)\left(n-1-d_{G}(v)\right).\]
Každé trojici vrcholů z $V$, která v grafu $G$ indukuje podgrafy
\begin{center}
%Title: K3_podgraf3.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:10:40 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 0.296 26.312 to 0.893 26.312
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312
}%
\linethickness=0pt
\putrectangle corners at 0.222 26.922 and 0.969 26.238
\endpicture}
\end{center}
nebo
\begin{center}
%Title: K3_podgraf4.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:10:56 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.298 26.312
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.597 26.848
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 0.891 26.314 to 0.296 26.314
\plot 0.296 26.314 0.595 26.848 /
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.893 26.312
}%
\linethickness=0pt
\putrectangle corners at 0.222 26.922 and 0.969 26.238
\endpicture},
\end{center}
však přísluší právě dva různé výběry vrcholu $v$, tj. právě dvě \emph{uspořádané}
trojice $(v,u,w)$ daných vlastností. Proto
\noindent \hfill{}
\begin{center}
%Title: K3_rovnice2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:29:20 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.561 26.253
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.263 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 2.857 25.718
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 3.095 25.897 center at 2.559 25.897
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 1.488 25.897 center at 0.953 25.897
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 1.251 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.654 25.718
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 0.953 26.253
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 2.857 25.718 to 2.261 25.718
\plot 2.261 25.718 2.559 26.255 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 0.654 25.718 to 1.249 25.718
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 1.607 25.777
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\frac{1}{2}\sum_{v \in V}d_{G}(v)\left(n-1-d_{G}(v)\right).}$}%
} [lB] at 3.274 25.777
\linethickness=0pt
\putrectangle corners at 0.385 26.513 and 3.306 25.330
\endpicture}
\end{center}
\hfill{}~
Toto číslo nyní odhadneme shora. Všechny členy sumy, které jsou tvaru
$x(n-1-x)$, jsou $\leq\left(\frac{n-1}{2}\right)^{2}$, protože graf
funkce $x(n-1-x)=-\left(x-\frac{n-1}{2}\right)^{2}+\left(\frac{n-1}{2}\right)^{2}$
je parabola s maximem $\left(\frac{n-1}{2}\right)^{2}$ v bodě $x=\frac{n-1}{2}$.
Tím současně odhadneme zdola počet $K_{3}$ a $\bar{K}_{3}$ v grafu
$G$:
\hfill{}
\begin{center}
%Title: K3_rovnice3.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:50:40 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 ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.908 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 16.609 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 17.204 18.574
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 17.441 18.754 center at 16.906 18.754
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 15.835 18.754 center at 15.299 18.754
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.598 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.001 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 15.299 19.109
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 17.204 18.574 to 16.607 18.574
\plot 16.607 18.574 16.906 19.111 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\putrule from 15.001 18.574 to 15.596 18.574
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 15.953 18.633
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 11.132 18.754 center at 10.596 18.754
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.894 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.298 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 10.596 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.205 19.109
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 11.906 18.574
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.119}}} at 12.501 18.574
}%
%
% Fig ELLIPSE
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.536:0.536 360 degrees
from 12.738 18.754 center at 12.203 18.754
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot 10.298 18.574 10.596 19.111 /
\plot 10.596 19.111 10.892 18.574 /
\putrule from 10.892 18.574 to 10.298 18.574
}%
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$\Bigg)\geq$}%
} [lB] at 17.560 18.633
%
% Fig TEXT object
%
\put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$=\displaystyle{\binom{n}{3}}-\Bigg($}%
} [lB] at 12.918 18.633
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$+$}%
} [lB] at 11.250 18.633
\linethickness=0pt
\putrectangle corners at 10.029 19.321 and 17.592 18.186
\endpicture}
\end{center}
\hfill{}~
\noindent \[
\geq\frac{n(n-1)(n-2)}{6}-n\cdot\frac{1}{2}\left(\frac{n-1}{2}\right)^{2}=\frac{n(n-1)\left(4(n-2)-3(n-1)\right)}{24}=\frac{n(n-1)(n-5)}{24}\]
\end{proof}
\subsection{Odhady $\alpha(G)$ a $\omega(G)$}
V této části přednášky se budeme zabývat odhady maximální velikosti
kliky a nezávislé množiny v grafu. Zopakujte si proto definici \ref{def:klika-nez-mnozina}
z první kapitoly.
\begin{obs}
Pro libovolný graf $G=(V,E)$, $n=\# V$, platí\[
\alpha(G)\geq\frac{n}{\Delta(G)+1}.\]
\end{obs}
\begin{proof}
Ukážeme konstrukci nezávislé množiny o velikosti alespoň $\frac{n}{\Delta(G)+1}$.
\begin{enumerate}
\item $S:=\emptyset$, $W:=V$.
\item Vezmeme libovolný vrchol $v\in W$ a přesuneme jej z množiny $W$
do množiny $S$. Všechny sousedy $v$ v grafu $G$ odstraníme z $W$.
Celkem tedy z $W$ odstraníme nejvýše $\Delta(G)+1$ vrcholů.
\item Krok 2 opakujeme, dokud $W\neq\emptyset$.
\end{enumerate}
Je zřejmé, že po provedení popsaného postupu bude $S$ nezávislá množina,
přičemž \[
\# S\geq\frac{n}{\Delta(G)+1}.\]
\end{proof}
\begin{thm}
\label{thm:odhad-alfa-G-pomoci-ro-G}Pro libovolný graf $G=(V,E)$
platí\[
\alpha(G)\geq\frac{n}{\rho(G)+1},\]
kde $\rho(G)$ je průměrný stupeň grafu $G$ (viz. definice \ref{def:stupen-vrcholu}).
\end{thm}
Tuto větu dokážeme za chvíli, neboť snadno vyplyne z věty \ref{thm:odhad-omega-G}.
Nejprve ukážeme slabší odhad $\alpha(G)$:
\begin{thm}
Nechť $G=(V,E)$ s průměrným stupněm $\rho(G)\geq1$. Potom\[
\alpha(G)\geq\frac{n}{2\Delta(G)}.\]
\end{thm}
\begin{proof}
Provedeme pravděpodobnostní důkaz tohoto tvrzení. Nechť $G$ je pevně
daný graf a označme jako vždy $n=\# V,m=\# E$. Sestrojme \underbar{indukovaný}
podgraf $H\subset G$ tak, že každý $v\in V$ zařadíme do $V(H)$
nezávisle s pravděpodobností $p\in[0,1]$, kde $p$ zatím nespecifikujeme.
Označme si náhodné veličiny
\begin{lyxlist}{00.00.0000}
\item [$X=\# V(H)$,]což je počet vrcholů grafu $H$, a
\item [$Y=\# E(H)$,]což je počet hran v grafu $H$.
\end{lyxlist}
Vypočítáme střední hodnoty těchto veličin obvyklým způsobem. Pro každý
$v\in V$ zavedeme elementární náhodnou veličinu\[
X_{v}=\begin{cases}
1 & v\in V(H)\\
0 & v\notin V(H)\end{cases}.\]
Potom\[
X=\sum_{v\in V}X_{v},\]
\[
\E X_{v}=1\cdot\Pr(X_{v}=1)+0\cdot\Pr(X_{v}=0)=1\cdot p+0\cdot p=p\]
a\[
\E X=\sum_{v\in V}\E X_{v}=np.\]
Obdobně vypočítáme střední hodnotu počtu hran. Pro každou hranu $e\in E$,
$e=\{ u,v\}$ zavedeme\[
Y_{e}=\begin{cases}
1 & e\in E(H)\\
0 & e\notin E(H)\end{cases}.\]
Potom\[
Y=\sum_{v\in V}Y_{e},\]
\[
\E Y_{e}=\Pr(Y_{e}=1)=\Pr(u\in V(H)\wedge v\in V(H))=p^{2}\]
a\[
\E Y=\sum_{e\in E}\E Y_{v}=mp^{2}.\]
Platí ale \[
\rho(G)=\frac{1}{n}\sum_{v\in V}d_{G}(V)=\frac{2m}{n}\quad\Rightarrow\quad\E Y=p^{2}\frac{\rho(G)\cdot n}{2}.\]
Zvolme nyní $p=\frac{1}{\rho(G)}$. Potom\[
\E(X-Y)=np-\frac{\rho(G)np^{2}}{2}=\frac{n}{\rho(G)}-\frac{n}{2\rho(G)}=\frac{n}{2\rho(G)}.\]
To znamená, že existuje taková konkrétní realizace indukovaného podgrafu
$H$, že\begin{equation}
X-Y\geq\frac{n}{2\rho(G)}.\label{eq:rozdil-hran-vrch}\end{equation}
Nyní odebereme všechny hrany z tohoto $H$ vždy společně s jedním
jejich koncem. Z původní množiny vrcholů $V(H)$ tak vznikne množina
vrcholů $S$, která je nezávislou množinou v grafu $G$. $H$ je totiž
indukovaný podgraf, takže mezi vrcholy z $S$ již nevedou žádné hrany
ani v grafu $G$. Po ubrání $Y$ hran spolu s $Y$ vrcholy zůstane
v $S$ podle vztahu (\ref{eq:rozdil-hran-vrch}) alespoň $\frac{n}{2\rho(G)}$
vrcholů, čímž je věta dokázána.
\end{proof}
\begin{thm}
\label{thm:odhad-omega-G}Pro libovolný graf $G=(V,E)$ platí\[
\omega(G)\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\]
\end{thm}
\begin{proof}
bude opět pravděpodobnostní. BÚNO předpokládejme $V=\hat{n}$. Náhodně
vybereme permutaci $\pi\in S_{n}$, které přiřadíme množninu $C_{\pi}\subset V$
takto:
\begin{itemize}
\item $\pi(1)\in C_{\pi}$
\item pro $i>1$ dáme vrchol $\pi(i)$ do $C_{\pi}$, pokud $\left(\forall j<i\right)\left(\{\pi(i),\pi(j)\}\in E\right)$,
tj. vrchol se dostane do $C_{\pi}$, jestliže je v hraně se všemi
předchozími vrcholy při jejich uspořádání podle permutace $\pi$.
\end{itemize}
$C_{\pi}$ je zřejmě klika v $G$. Její velikost je náhodná veličina,
kterou označíme $X$. Nyní postupujeme jako obvykle: Ukážeme-li \[
\E X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)},\]
bude důkaz hotov, protože pak existuje konkrétní $C_{\pi}$, pro niž
je $X\geq\sum_{v\in V}\frac{1}{n-d_{G}(v)}$. Pro každé $v\in V$
definujeme\[
X_{v}=\begin{cases}
1 & v\in C_{\pi}\\
0 & v\notin C_{\pi}\end{cases}.\]
Potom\[
\E X_{v}=\Pr(v\in C_{\pi})=\frac{1}{n-d_{G}(v)},\]
což nyní dokážeme. Aby $v\in C_{\pi}$, tak vrcholy, se kterými $v$
není v hraně, musí být v permutaci $\pi$ umístěny až za ním. Na umístění
jeho sousedů nezáleží. Počet vrcholů, se kterými $v$ není v hraně,
a to včetně vrcholu $v$ samotného, je $n-d_{G}(v)$. Počet způsobů,
kterými lze $n-d_{G}(v)$ vrcholů uspořádat tak, aby $v$ byl na prvním
místě, je $\left(n-d_{G}(v)-1\right)!$. Počet všech uspořádání $n-d_{G}(v)$
vrcholů je $\left(n-d_{G}(v)\right)!$, a proto\[
\Pr(v\in C_{\pi})=\frac{\left(n-d_{G}(v)-1\right)!}{\left(n-d_{G}(v)\right)!}=\frac{1}{n-d_{G}(v)}\]
Konečně tedy můžeme vyčíslit\[
\E X=\sum_{v\in V}X_{v}=\sum_{v\in V}\frac{1}{n-d_{G}(v)}.\]
\end{proof}
Důsledkem této věty je věta \ref{thm:odhad-alfa-G-pomoci-ro-G}, kterou
nyní dokážeme.
\begin{proof}
Nechť $G$ je libovolný graf. Potom podle předchozí věty je\[
\omega(\bar{G})\geq\sum_{v\in V}\frac{1}{n-d_{\bar{G}}(v)},\]
přičemž platí $d_{\bar{G}}(v)=n-1-d_{G}(v)$ a $\alpha(G)=\omega(\bar{G})$.
Proto\begin{equation}
\alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}.\label{eq:odhad-alfa-G}\end{equation}
Protože funkce $\frac{1}{1+x}$ je na intervalu $[0,+\infty)$ konvexní,
můžeme podle Jensenovy nerovnosti \ref{lem:jensenova-nerovnost} provést
odhad\[
\frac{n}{1+\frac{1}{n}\sum\limits _{i=1}^{n}x_{i}}\leq\sum_{i=1}^{n}\frac{1}{1+x_{i}}.\]
Pokud jej použijeme na vztah (\ref{eq:odhad-alfa-G}), dostaneme\[
\alpha(G)\geq\sum_{v\in V}\frac{1}{1+d_{G}(v)}\geq\frac{n}{1+\frac{1}{n}\sum\limits _{v\in V}d_{G}(v)}=\frac{n}{1+\rho(G)}.\]
\end{proof}
Pomocí věty \ref{thm:odhad-omega-G} můžeme provést i alternativní
důkaz Turánovy věty \ref{thm:turan}, která říká: Pokud $G=(V,E)$
neobsahuje kliku $K_{p}$, tak $\# E\leq\frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right)$
.
Vyjdeme ze Schwarzovy nerovnosti na prostoru $\R^{n}$ se standardním
skalárním součinem. Pro $\vec{x},\vec{y}\in\R^{n}$ platí\[
\left|\left(\vec{x},\vec{y}\right)\right|^{2}\leq\left\Vert \vec{x}\right\Vert ^{2}\left\Vert \vec{y}\right\Vert ^{2}.\]
Nechť $G=(V,E)$, $V=\hat{n}$. Označme $d_{i}=d_{G}(i)$ pro každé
$i\in V$ a zvolme konkrétně\begin{eqnarray*}
\vec{x} & = & \left(\frac{1}{\sqrt{n-d_{1}}},\frac{1}{\sqrt{n-d_{2}}},...,\frac{1}{\sqrt{n-d_{n}}}\right),\\
\vec{y} & = & \left(\sqrt{n-d_{1}},\sqrt{n-d_{2}},...,\sqrt{n-d_{n}}\right).\end{eqnarray*}
Potom má Schwarzova nerovnost tvar\begin{equation}
n^{2}=\underbrace{\left(\sum_{i=1}^{n}\frac{1}{\sqrt{n-d_{i}}}\sqrt{n-d_{i}}\right)}_{\left|\left(\vec{x},\vec{y}\right)\right|^{2}}\leq\underbrace{\sum_{i=1}^{n}\frac{1}{n-d_{i}}}_{\left\Vert \vec{x}\right\Vert ^{2}}\underbrace{\sum_{j=1}^{n}(n-d_{j})}_{\left\Vert \vec{y}\right\Vert ^{2}}.\label{eq:schwarz-turan}\end{equation}
Protože podle předpokladu $G$ neobsahuje $K_{p}$, platí podle věty
\ref{thm:odhad-omega-G}\[
\sum_{i=1}^{n}\frac{1}{n-d_{i}}\leq\omega(G)\leq p-1.\]
Po dosazení do \ref{eq:schwarz-turan} dostáváme\begin{eqnarray*}
n^{2} & \leq & (p-1)\left(n^{2}-2\# E\right)\\
2(p-1)\# E & \leq & (p-2)n^{2}\\
\# E & \leq & \frac{n^{2}}{2}\left(1-\frac{1}{p-1}\right).\end{eqnarray*}
\begin{thm}
\label{thm:posloupnost-nahod-grafu}Nechť $G_{n}$ označuje náhodný
graf na $n$ vrcholech%
\footnote{$G_{n}$ vznikne tak, že každé dva vrcholy spojíme hranou s pravděpodobností
$\frac{1}{2}$. ,,Náhodná veličina{}`` $G_{n}$ má potom rovnoměrné
rozdělení.%
}. Potom existuje posloupnost $\left(k_{n}\right)_{n\in\N}$ taková,
že\begin{equation}
\lim_{n\to\infty}\Pr\left(\left(\omega(G_{n})=k_{n}\right)\vee\left(\omega(G_{n})=k_{n}+1\right)\right)=1\label{eq:posloupnost_kn}\end{equation}
\end{thm}
\begin{rem*}
~
\begin{itemize}
\item Pro posloupnost $\left(k_{n}\right)_{n\in\N}$ platí řádově\[
\lim_{n\to\infty}\frac{k_{n}}{2\log_{2}n}=1.\]
\item Je-li $G_{n}$ náhodný graf, potom $\bar{G}_{n}$ je také náhodný
graf, a přitom $\omega(\bar{G}_{n})=\alpha(G_{n})$. Proto je (\ref{eq:posloupnost_kn})
ekvivalentní s\[
\lim_{n\to\infty}\Pr\left(\left(\alpha(G_{n})=k_{n}\right)\vee\left(\alpha(G_{n})=k_{n}+1\right)\right)=1.\]
\end{itemize}
\end{rem*}
