\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
