\input /home/pasky/school/fastex/lib.tex

\subchapter{Počítání dvěma způsoby}{

	\scpart{Princip sudosti}{
		$$\forall G=(V,E):\ \sum_{v\in V}\deg v = 2|E|$$

		\proof{
			Dvojím způsobem spočítáme počet dvojic
			$(v,e)$, kde $v\in V$, $e\in E$, $v\in e$.
			--- jednou podle vrcholů a pak podle hran.

			$$ \sum_{v\in V}\deg v = \undernote{\sum_{e\in E}2}{2|E|}$$

			\qed
		}
	}

	\scpart{Nezávislý systém množin}{
		\definition{
			Mějme množinu $X$, $M \subseteq P(x)$ nazýváme
			{\bf nezávislý systém množin}, pokud
			$$\forall A,B \in M:\ A\ne B \Rightarrow A \not\subset B$$
		}

		\theorem{}{Spernerova}{
			$X$ buď množina velikosti $n$. Potom maximální
			velikost nezávislého systému množin
			$\sM \subseteq P(x)$ je rovna $\cn{n}{\floor{n\over2}}$
			(např. v Pascalově $\triangle$ je to v řádku, jehož
			součet je $2^n$, největší číslo).

			\examples{
			\list{
			\listItem{$n=3$:

				$$\eqalign{X&=\{1,2,3\}\cr
					  M_1&=\{\{1,2\},\{1,3\},\{2,3\}\}\cr
					  M_2&=\{\{1\},\{2\},\{3\}\}}$$
				jsou nezávislé systémy množin velikosti
				$$\cn{3}{1} = 3$$
			}
			\listItem{obecné $n$:

				$M :=$ množina $\floor{n/2}$-prvkových podmnožin množiny $X = \{1,2,\ldots,n\}$.
				Pak $M$ bude nezávislý systém velikosti $\cn{n}{\floor{n/2}}$.
			}
			}
			}

			\proof{
			\list{
			\nlistItem{Maximální velikost $\ge \cn{n}{\floor{n\over2}}$: z předchozího příkladu.}
			\nlistItem{Maximální velikost $\le \cn{n}{\floor{n\over2}}$:

				$X$, $M$ podle předpokladů.

				\shortdef{Maximální řetězec}{$R=\{0,\{x_1\},\{x_1,x_2\},\ldots,
						\undernote{\{x_1,x_2,\ldots,x_n\}}{X}\}$
					kde $x_1$, \dots, $x_n$ je libovolná permutace prvků $X$.
					Maximálních řetězců je $n!$, navíc kdykoliv si vezmeme
					libovolné dvě množiny z maximálního řetězce,
					jedna bude vždy podmnožinou druhé.}

				\def\cM{{\cal M}} % TODO: Pojmenovat nejak lepe? --pasky

				Spočítáme dvěma způsoby počet dvojic $(R,\cM)$ takových, že $\cM \in R$.
				$R$ buď maximální řetězec, $\cM$ pak množina z $M$.

				Tento počet je:
				\list{
				\alistItem{$\le (\#$maximálních řetězců$) = n!$

					Kdyby do jednoho $R$ patřily dvě $\cM$,
					nepatřily by obě do nezávislého systému množin.
				}
				\alistItem{$= \sum_{\cM\in M}\undernote{|\cM|!(n-|\cM|)!}
									{\textstyle\#\textbox{max. řetězců}\atop
									 \textstyle\textbox{obsahujících} \cM}$.
				}
				}

				Tedy:
				$$n! \ge \sum_{\cM\in M}|\cM|!(n-|\cM|)!$$
				$$1  \ge \sum_{\cM\in M}{|\cM|!(n-|\cM|)!\over n!} = \sum_{\cM\in M}{1\over\cn{n}{|\cM|}}
					\ge \sum_{\cM\in M}{1\over\cn{n}{\floor{n\over2}}}
					= |M|{1\over\cn{n}{\floor{n\over2}}}$$
				$$ |M| \le \cn{n}{\floor{n\over2}} $$
			}
			}
				\qed
			}
		}
	}

	\scpart{Grafy bez $K_{2,2}$ ($C_4$)}{
		\theorem{}{o počtu hran na $n$ vrcholech}{
			Nechť $G=(V,E)$ je graf na $n$ vrcholech neobsahující $K_{2,2}$.
			Potom
			$$|E| \le {n\sqrt{n}+n\over2}$$

			\proof{
				Využijeme {\bf \ref{Cauchy-Schwarz}ovu nerovnost}:

				$$\sum_{i=1}^n x_iy_i \le \sqrt{\sum_{i=1}^n x_i^2} \cdot \sqrt{\sum_{i=1}^n y_i^2}$$
				pro libovolné $x_1,\ldots,x_n,y_1,\ldots,y_n\in\real$.

				Počítáme dvěma způsoby počet podgrafů (cest) {\tt u - v - u'}.
				Tento počet je:
				\list{
				\alistItem{$\le \cn{n}{2}$:
					pro $\forall u,u'\in V$, $u\ne u'$
					existuje nejvýše jeden $v\in V$ takový,
					že $\{u,v\}, \{u',v\} \in E$ --- jinak
					dostaneme $K_{2,2}$:
\asciiart{
*-* u
 X
*-* u'
}
				}
				\alistItem{$= \sum_{v\in V}\cn{\deg v}{2}$:
					pro $\forall v \in V$ máme právě
					$\cn{\deg v}{2}$ vidliček {\tt * - v - *}.
				}
				}

				Tedy:
				$$\eqmalign{\sum_{n\in V} \cn{\deg v}{2} &\le& \cn{n}{2}                   &\le& {1\over2}n^2\cr
				   {1\over2}\sum_{n\in V} ((\deg v)-1)^2 &\le& \sum_{v\in V} \cn{\deg v}{2}&\le& {1\over2}n^2\cr
				   \undernote{\sum_{v\in V}((\deg v)-1)\cdot1}{2|E|-n}
					&\le& \undernote{\sqrt{\sum_{v\in V}((\deg v)-1)^2}}{\le \sqrt{n^2}}
				        \cdot\undernote{\sqrt{\sum_{v\in V}1^2}}{\sqrt{n}}
					&\le& n\sqrt{n}}$$
				$$ |E|\le{1\over2}(n\sqrt{n}+n) $$

				\qed
			}
		}
	}
}

\bend