this dir | view | cards | source | edit | dark top

Kombinatorika a grafy 1

Kombinatorika a grafy 1

Odhady na kombinatorické funkce

lemma: $n^{n/2}\leq n!\leq n^n$

horní odhad jednoduchý
dolní odhad
- součin prvního a posledního, druhého a předposledního, … prvku součinu faktoriálu je vždy $\geq n$
- aby byl počet činitelů faktoriálu sudý, použijeme $(n!)^2$
- takže $(n!)^2=\prod_{i=1}^n(i\cdot(n+1-i))\geq n^n$
- proto $n!\geq n^{n/2}$
- to, že $i(n+1-i)\geq n$ , lze dokázat graficky pomocí funkce $f(x)=x(n+1-x)$
důsledek $\sqrt n\leq \sqrt[n]{n!}\leq n$
$\sqrt[n]{n!}$ se chová trochu jako $\frac n2$

Odhady na kombinatorické funkce

věta: $e(\frac ne)^n\leq n!\leq en(\frac ne)^n$

u zkoušky můžeme použít libovolný korektní důkaz (obecně u všech vět)
důkaz 1: indukcí s využitím $e^x\geq 1+x$
důkaz 2: odhad pomocí integrálu $\ln(n!)=\sum_{i=1}^n\ln(i)=\sum_{i=2}^n\ln(i)$ $ln (n!) = \sum_{i = 1}^{n} ln (i) = \sum_{i = 2}^{n} ln (i)$
- schodovitá plocha, kde schod má šířku 1 a výšku $\ln(i)$ má obsah daný uvedeným součtem
- obsah schodovité plochy je zdola odhadnutý obsahem plochy pod křivkou logaritmu
- $\ln(n!)\geq\int_1^n\ln(x)\,dx=[x\ln(x)-x]^n_1=(n\ln n-n+1)=:I_n$
- $n!\geq e^{I_n}=e^{n\ln n-n+1}=e(\frac ne)^n$
- obdobně dolní odhad
  - $\ln((n-1)!)\leq I_n$
  - $e^{I_n}\geq(n-1)!\implies n\cdot e^{I_n}\geq n!\implies n\cdot e(\frac ne)^n\geq n!$
důkaz 3: jen $(\frac ne)^n\leq n!$ $(\frac{n}{e})^{n} \leq n!$
- víme z analýzy, že $e^x=1+x+\frac{x^2}{2}+\frac{x^3}{3!}+\dots+\frac{x^k}{k!}+\dots=\sum^\infty_{k=0}\frac{x^k}{k!}$
- pro $x\geq 0:e^x\geq\frac {x^n}{n!}$ (protože Taylorova řada určitě někde obsahuje $x^n\over n!$ )
- tedy $n!\geq \frac{x^n}{e^x}\implies n!\geq \frac{n^n}{e^n}=(\frac ne)^n$ (platí to pro libovolné $x\geq 0$ , takže dosadíme $x=n$ )

Odhady na kombinatorické funkce

kombinační číslo ${n\choose k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot(n-1)\cdots(n-k+1)}{k\cdot(k+1)\cdots1}$

jeho odhad…

Odhady na kombinatorické funkce

důkaz

definujme $P:=\frac{2m\choose m}{2^{2m}}$ a dokažme $\frac1{2\sqrt{m}}\leq P\leq \frac{1}{\sqrt{2m}}$
…

Vytvořující (generující) funkce

definice: vytvořující funkce posloupnosti $(a_n)_{n=0}^\infty$ reálných čísel je funkce proměnné $x$ definovaná jako součet $f(x)=\sum_{n=0}^\infty a_n(x^n)$

tato funkce nemusí být dobře definovaná pro všechna reálná čísla (dokonce se může stát, že nebude definovaná pro žádné reálné číslo kromě nuly)
pro nás bude praktické, když bude definovaná na okolí nuly (více než jednobodovém)

Vytvořující (generující) funkce

navíc má $f(x)=\sum_{n=0}^\infty a_nx^n$ derivace všech řádů na $(-\frac 1K,\frac 1K)$ , které se dají spočítat „derivováním člen po členu“

$f'(x)=\sum_{n=0}^\infty a_nnx^{n-1}$
$f''(x)=\sum_{n=0}^\infty a_nn(n-1)x^{n-2}$
$f(x)=a_0+a_1x+a_2x^2+a_3x^3+\dots$
$f'(x)=a_1+2a_2x+3a_3x^2+\dots$
$f''(x)=2a_2+3\cdot 2a_3+\dots$
$f^{(n)}(x)=n!\cdot a_n+\dots$

Vytvořující (generující) funkce

důsledek

$f(0)=a_0$
$f'(0)=a_1$
$f''(0)=2a_2$
$f^{(n)}(0)=n!\cdot a_n$
takže $a_n=\frac{1}{n!} f^{(n)}(0)$

Vytvořující (generující) funkce

užití vytvořujících funkcí

kombinatorické počítání
asymptotické odhady
dokazování identit u posloupností
řešení rekurencí

Vytvořující (generující) funkce

příklad na kombinatorické počítání – platíme $n$ Kč pomocí mincí s hodnotami 1, 2 a 5 Kč, na pořadí nezáleží ( $a_n$ je počet způsobů, jak $n$ korun zaplatit)

$f(x)=\sum_{n=0}^\infty a_nx^n=$
$=(1+x+x^2+x^3+\dots)(1+x^2+x^4+x^6+\dots)(1+x^5+x^{10}+\dots)$
$=\frac1{1-x}\cdot\frac1{1-x^2}\cdot\frac1{1-x^5}$
pak lze zjistit koeficient u $x^n$ , ten se bude rovnat $a_n$

Vytvořující (generující) funkce

Fibonacciho čísla $F_0:=0,\,F_1:=1,\,F_n:=F_{n-1}+F_{n-2}$ pro $n\geq 2$

chceme získat explicitní vzorec pro $f(x)=\sum_{n=0}^\infty F_nx^n$
obecná metoda řešení rekurencí
- vezmi rekurenci pro $n\geq n_0$
- vynásob ji $x^n$
- sečti pro $n\geq n_0$
- vyjádři všechny sumy pomocí hledané vytvořující funkce $f(x)$
- dopočítej $f(x)$
aplikace na $F_n$ $F_{n}$
- $F_n=F_{n-1}+F_{n-2}$ pro $n\geq 2$
- $F_nx^n=F_{n-1}x^n+F_{n-2}x^n$ pro $n\geq 2$
- $\underbrace{\sum_{n=2}^\infty F_nx^n}_{S_1}=\underbrace{\sum_{n=2}^\infty F_{n-1}x^n}_{S_2}+\underbrace{\sum_{n=2}^\infty F_{n-2}x^n}_{S_3}$ $S_{1} n = 2 \sum \infty F_{n} x^{n} = S_{2} n = 2 \sum \infty F_{n - 1} x^{n} + S_{3} n = 2 \sum \infty F_{n - 2} x^{n}$
  - $S_1=F_2x^2+F_3x^3+F_4x^4+\dots=f(x)-F_0-F_1x$
  - $S_2=F_1x^2+F_2x^3+F_3x^4+\dots=x(f(x)-F_0)$
  - $S_3=F_0x^2+F_1x^3+F_2x^4+\dots=x^2f(x)$
  - $S_1=S_2+S_3$
  - $f(x)-F_0-F_1x=x(f(x)-F_0)+x^2f(x)$
  - $f(x)-xf(x)-x^2f(x)=F_0+F_1x-F_0x$
  - $f(x)\cdot(1-x-x^2)=F_0+F_1x-F_0x$
  - $f(x)=\frac{F_0+F_1x-F_0x}{1-x-x^2}=\frac x{1-x-x^2}$

Vytvořující (generující) funkce

obecnější příklad – mějme posloupnost $a_0,a_1,a_2,\dots$ , která splňuje $a_n=\alpha_1a_{n-1}+\alpha_2a_{n-2}+\dots+\alpha_da_{n-d}$ pro každé $n\geq d$ , kde $d\in\mathbb N$ , $\alpha_1,\dots,\alpha_d\in\mathbb R,\,\alpha_d\neq 0$ ; najděme vzorec pro $f(x)=\sum_{n=0}^\infty a_nx^n$

$\sum_{n=d}^\infty a_nx^n=$
$=\sum_{n=d}^\infty\alpha_1a_{n-1}x^n+\sum_{n=d}^\infty\alpha_2a_{n-2}x^n+\dots+\sum_{n=d}^\infty\alpha_da_{n-d}x^n$
$f(x)-(a_0+a_1x+\dots+a_{d-1}x^{d-1})=$
$=a_1x(f(x)-(a_0+a_1x+\dots+a_{d-2}x^{d-2}))+$
$+a_2x^2(f(x)-(a_0+\dots+a_{d-3}x^{d-3}))+\dots+a_dx^df(x)$
…

Vytvořující (generující) funkce

pro $\alpha,\beta,\gamma\in\mathbb R,\,\beta\neq0:\frac\alpha{\beta+\gamma x}=\frac\alpha\beta\cdot\frac1{1-(-\frac\gamma\beta x)}$

z toho už umím najít původní vzorec vytvořující funkce pomocí $\frac1{1-x}$

Vytvořující (generující) funkce

víme: binomická věta

pro $d\in\mathbb N_0:(1+x)^d=\sum_{n=0}^d{d\choose n}x^n$
tedy $(1+x)^d$ je vytvořující funkcí pro ${d\choose 0},{d\choose1},{d\choose2},\dots,{d\choose d},0,0,0,\dots$

Vytvořující (generující) funkce

věta: zobecněná binomická věta

pro $\delta\in\mathbb R$ platí $(1+x)^\delta=\sum_{n=0}^\infty{\delta\choose n}x^n$
nekonečno bychom mohli použít i u základní binomické věty, pokud bychom použili zobecněné kombinační číslo
celkově ignorujeme otázky konvergence, ale aby věta platila, tak bychom chtěli $|x|\lt1$

Vytvořující (generující) funkce

dk: označme $f(x)=(1+x)^\delta$

vidíme
- $f'(x)=\delta(1+x)^{\delta-1}$
- $f''(x)=\delta(\delta-1)(1+x)^{\delta-2}$
- $\quad\vdots$
- $f^{(n)}(x)=\delta(\delta-1)\cdot\ldots\cdot(\delta-n+1)(1+x)^{\delta-n}$
- $\quad\vdots$
nechť $a_0,a_1,\dots$ je posloupnost s vytvořující funkcí $f(x)$
potom $a_n=\frac{f^{(n)}(0)}{n!}={\delta\choose n}\quad\square$

Vytvořující (generující) funkce

důsledek

pro $d\in\mathbb N_0:\frac1{(1-x)^d}=(1+(-x))^{-d}=_{\text{ZBV}}$
…

Vytvořující (generující) funkce

důsledek důsledku

$\frac\alpha{(\beta+\gamma x)^d}=\frac\alpha{\beta^d}\cdot\frac1{(1-(-\frac\gamma\beta x))^d}=\sum_{n=0}^\infty\frac{\alpha}{\beta^d}{n+d-1\choose d-1}(-\frac\gamma\beta)^nx^n$
čeho je vytvořující funkce $f(x)=\frac\alpha{\gamma x}$ ? ničeho, protože $f(x)$ nelze spojitě dodefinovat v nule (kromě $\alpha=0$ , potom $f(x)=0$ )

Vytvořující (generující) funkce

fakt

mějme funkci $f(x)=\frac{P(x)}{Q(x)}$ , kde $P(x)$ a $Q(x)$ jsou polynomy a stupeň $P(x)$ je menší než stupeň $Q(x)$
nechť $Q(x)$ má navzájem různé reálné kořeny $\rho_1,\rho_2,\dots,\rho_k$ a nechť $n_i$ označuje násobnost kořenu $\rho_i$
předpokládejme, že $Q(x)$ nemá nereálné kořeny, tedy $Q(x)=\gamma\cdot(x-\rho_1)^{n_1}\cdot(x-\rho_2)^{n_2}\cdot\ldots\cdot(x-\rho_k)^{n_k}$ , kde $\gamma\in\mathbb R$
potom $f(x)$ se dá vyjádřit jako součet parciálního zlomků pro kořeny $\rho_1,\dots,\rho_k$ , kde parciální zlomky pro $\rho_i$ mají stupeň nejvýš $n_i$
jinými slovy $\exists\alpha_{ij}\in\mathbb R:f(x)=\sum_{i=1}^k\sum_{j=1}^{n_i}\frac{\alpha_{ij}}{(x-\rho_i)^j}$
tohle je „dětská verze“ parciálních zlomků, důkaz nemusíme znát
poznámka
- pokud $P(x)$ má aspoň tak velký stupeň jako $Q(x)$ , tak pomocí dělení se zbytkem lze $P(x)$ vyjádřit jako $P'(x)\cdot Q(x)+Z(x)$ pro nějaké $P'(x)$ a $Z(x)$ , kde $Z(x)$ , kde $Z(x)$ má menší stupeň než $Q(x)$ , a tedy $\frac{P(x)}{Q(x)}=P'(x)+\frac{Z(x)}{Q(x)}$
tohle všechno nám umožňuje najít posloupnost k dané vytvořující funkci (která je podílem dvou polynomů)
(jednodušší) rozklad na parciální zlomky bychom mohli umět ke zkoušce

Vytvořující (generující) funkce

příklad: Fibonacciho čísla $f(x)=\sum F_nx^n=\frac x{1-x-x^2}$

kořeny $1-x-x^2:\rho_1=\frac{1-\sqrt5}{-2}=\frac{\sqrt5-1}{2},\,\rho_2=\frac{1+\sqrt5}{-2}=\frac{-1-\sqrt5}2$
$1-x-x^2=\gamma(x-\rho_1)(x-\rho_2)=-(x-\rho_1)(x-\rho_2)=$
$=-\rho_1\rho_2(1-\frac x{\rho_1})(1-\frac x{\rho_2})=(1-\frac x{\rho_1})(1-\frac x{\rho_2})$
$\frac{x}{1-x-x^2}=\frac{\alpha}{1-\frac{x}{\rho_1}}+\frac{\beta}{1-\frac x{\rho_2}}$ pro nějaké $\alpha,\beta\in\mathbb R$
$x=\alpha(1-\frac{x}{\rho_2})+\beta(1-\frac{x}{\rho_1})$ $x = α (1 - \frac{x}{ρ _{2}}) + β (1 - \frac{x}{ρ _{1}})$
- dosazením $x=0:\quad0=\alpha+\beta$
- dosazením $x=\rho_2:\quad\rho_2=\beta(1-\frac{\rho_2}{\rho_1})$
- z toho se dá vyjádřit $\alpha$ i $\beta$ pomocí $\rho$
$\alpha=\frac1{\sqrt5}$
$\beta=-\frac1{\sqrt5}$
tak se dá dojít k explicitnímu vzorci pro Fibonacciho čísla

Vytvořující (generující) funkce

df: binární strom je zakořeněný strom, jehož každý vnitřní vrchol má 2 potomky, na pořadí potomků záleží

$C_n$ $C_{n}$ … počet binární stromů s $n$ $n$ vnitřními vrcholy
- $C_0=1$
- $C_1=1$
- $C_2=2$
- $C_3=5$
$(C_n)_{n=0}^\infty$ jsou Catalanova čísla
$C(x):=\sum_{n=0}^\infty C_nx^n$
$C_0=1$
mějme kořen, levý syn je list, pravý podstrom má $n-1$ vnitřních vrcholů → počet možných pravých podstromů je $C_{n-1}$
nebo levý podstrom má jeden vnitřní vrchol a pravý $n-2$ , pak $C_1\cdot C_{n-2}$ možností
obecně levý podstrom $i$ vnitřních vrcholů, pravý $n-1-i$ vnitřních vrcholů, pak $C_i\cdot C_{n-1-i}$ možností
$C_n=C_0C_{n-1}+C_1C_{n-2}+\dots+C_{n-1}C_0=\sum_{i=0}^{n-1}C_iC_{n-1-i}$ $C_{n} = C_{0} C_{n - 1} + C_{1} C_{n - 2} + \dots + C_{n - 1} C_{0} = \sum_{i = 0}^{n - 1} C_{i} C_{n - 1 - i}$
- pro $n\geq 1$
$\sum_{n=1}^\infty C_nx^n=\sum_{n=1}^\infty\left(\sum_{i=0}^{n-1}C_iC_{n-1-i}\right)x^n$
$C(x)-1=x\sum_{n=0}^\infty\left(\sum_{i=0}^{n}C_iC_{n-i}\right)x^n$
$C(x)-1=x\cdot C^2(x)$
$xC^2(x)-C(x)+1=0$
2 řešení
- $\frac{1+\sqrt{1-4x}}{2x}=:C^+(x)$
- $\frac{1-\sqrt{1-4x}}{2x}=:C^-(x)$
chceme $C(0)=C_0=1$
$C^-(x)$ lze spojitě dodefinovat v nule, takže $C(x)=C^-(x)$
značení: $[x^n]f(x)$ je člen s indexem $n$ v posloupnosti, jejíž vytvořující funkce je $f(x)$
$C_n:=[x^n]\frac{1-\sqrt{1-4x}}{2x}=[x^{n+1}]\frac{1-\sqrt{1-4x}}{2}=[x^{n+1}](\frac12-\frac{\sqrt{1-4x}}{2})=$ $C_{n} := [x^{n}] \frac{1 - 1 - 4 x}{2 x} = [x^{n + 1}] \frac{1 - 1 - 4 x}{2} = [x^{n + 1}] (\frac{1}{2} - \frac{1 - 4 x}{2}) =$
- konstanta nám ovlivňuje koeficient u $C_0$ , můžeme se jí zbavit
$=-\frac12[x^{n+1}]\sqrt{1-4x}=$ $= - \frac{1}{2} [x^{n + 1}] 1 - 4 x =$
- …

Projektivní roviny

df: hypergraf je dvojice $(V,H)$ , kde $H$ je množina podmnožin $V$ , tj. $H\subseteq\mathcal P(V)$

prvky $V$ … vrcholy
prvky $H$ … hyperhrany
graf incidence hypergrafu $(V,H)$ je bipartitní graf s partitami $V$ a $H$ , kde mezi $x\in V$ a $h\in H$ vede hrana $\iff x\in h$
hyperhrany jsou jakoby množiny vrcholů

Projektivní roviny

df: projektivní rovina je hypergraf $(X,\mathcal P)$ takový, že platí tři axiomy:

A1: $(\forall x,y\in X,\;x\neq y)(\exists! p\in\mathcal P):\set{x,y}\subseteq p$ $(\forall x, y \in X, x \neq = y) (\exists! p \in P) : {x, y} \subseteq p$
- dva různé body určují právě jednu přímku
A2: $\forall p,q\in\mathcal P,\;p\neq q:|p\cap q|=1$ $\forall p, q \in P, p \neq = q : ∣ p \cap q ∣ = 1$
- každé dvě přímky mají jeden průsečík
A3: $(\exists Č\subseteq X,\;|Č|=4)(\forall p\in\mathcal P):|p\cap Č|\leq 2$ $(\exists \overset{ˇ}{C} \subseteq X, ∣ \overset{ˇ}{C} ∣ = 4) (\forall p \in P) : ∣ p \cap \overset{ˇ}{C} ∣ \leq 2$
- existuje množina čtyř bodů „v obecné poloze“ (žádné tři z nich neleží na přímce)
prvky $X$ … body
prvky $\mathcal P$ … přímky

Projektivní roviny

příklady projektivních rovin

Fanova rovina
rozšířená reálná eukleidovská rovina
- musíme dodefinovat „body v nekonečnu“ – pro každý možný směr rovnoběžek přidáme abstraktní bod, tyhle abstraktní body spojíme přímkou
karetní hra Dobble (splňuje alespoň jeden axiom – možná všechny?)

Projektivní roviny

příklad projektivní roviny

mějme body $a,b,c,d$
přímky
- $\set{a,b,e}$
- $\set{b,c,g}$
- $\set{c,d,e}$
- $\set{a,d,g}$
- $\set{a,c,f}$
- $\set{b,d,f}$
$e,f,g$ jsou průsečíky kvůli druhému axiomu
musíme dodat přímku $\set{e,f,g}$
tím dostáváme Fanovu rovinu (7 bodů, 7 přímek)

Projektivní roviny

dk: sporem

nechť v KPR $(X,\mathcal P)$ existují přímky $p,q$ takové, že $|p|\lt |q|$
označme $x$ společný bod $p,q$
nechť $p$ obsahuje body $x,y_1,y_2,\dots,y_k$ a $q$ obsahuje body $x,z_1,z_2,\dots,z_l$ , kde $k\lt l$
tvrdím, že existuje bod $w\in X$ , který nepatří do $p\cup q$ : volme $Č$ dle A3
pokud $Č\setminus(p\cup q)\neq\emptyset$ , volme $w\in Č\setminus(p\cup q)$
pokud $Č\subseteq p\cup q$ $\overset{ˇ}{C} \subseteq p \cup q$ , pak $|Č\cap p| = |Č\cap q|=2$ $∣ \overset{ˇ}{C} \cap p ∣ = ∣ \overset{ˇ}{C} \cap q ∣ = 2$ , BÚNO $Č=\set{y_1,y_2,z_1,z_2}$ $\overset{ˇ}{C} = {y_{1}, y_{2}, z_{1}, z_{2}}$
- v tom případě zvolíme za $w$ společný bod $\overline{y_1z_1}$ a $\overline{y_2z_2}$
kdyby $w\in p$ , tak $w$ je jediný společný bod $p$ a $\overline{y_1z_1}$ , a tedy $w=y_1$ , ale $w\in\overline{y_2z_2}$ , tedy $y_1=w\in\overline{y_2z_2}$ , tedy $|Č\cap \overline{y_2z_2}|\geq |\set{y_1,y_2,z_2}|=3$ , což je spor s volbou $Č$
uvažme přímky $\overline{w,z_1},\overline{w,z_2},\dots,\overline{w,z_l},\overline{w,x}$ , každá z nich protíná $p$ , jsou navzájem různé, tedy existuje bod $v\in p$ , který je obsažen v aspoň dvou z těch přímek $\overline{wz_1},\dots,\overline{wz_l},\overline{wx}$
spor: $w$ a $v$ mají aspoň 2 společné přímky $\quad\square$

Projektivní roviny

def: KPR má řád $n\in\mathbb N$ , pokud každá její přímka má $n+1$ bodů

tedy řád KPR := velikost přímky – 1

Projektivní roviny

důkaz

volme Č dle A3
volme 3 různé body $a,b,c\in Č\setminus\set x$
tvrdím, že alespoň jedna z přímek $\overline{ab},\overline{ac}$ neobsahuje $x$
jinak by $\set{a,x}\subseteq\overline{ac}\cap\overline{ab}$ , což je spor

Projektivní roviny

tvrzení: pro KPR $(X,\mathcal P)$ řádu $n$ platí následující

každý bod patří do právě $n+1$ přímek
$|X|=n^2+n+1$
$|\mathcal P|=n^2+n+1$

Projektivní roviny

důkaz

první bod
- volme $x\in X$
- dle lemmatu $\exists p\in\mathcal P:x\notin p$
- označme $p=\set{y_1,y_2,\dots,y_{n+1}}$
- definujme přímky $q_1,q_2,\dots,q_{n+1}$ , kde $q_i=\overline{xy_i}$
- tvrdíme, že pro $i\neq j$ $i \neq = j$ je $q_i\neq q_j$ $q_{i} \neq = q_{j}$
  - kdyby ne, tak $\set{y_i,y_j}\subseteq q_i\cap p$ , což je spor
- tvrdíme, že $\forall r\in\mathcal P:$ pokud $x\in r$ , tak $r\in\set{q_1,\dots,q_{n+1}}$
- volme $r\in\mathcal P$ takovou, že $x\in r$ , jistě $|r\cap p|=1$ , nechť $y_i$ je prvek $r\cap p$ , potom $r=\overline{xy_i}=q_i$
- tedy bodem $x$ prochází právě $n+1$ přímek
druhý bod
- volme $x\in X$ , nechť $p_i$ jsou přímky procházející $x$
- všimněme si, že každý bod $y\in X\setminus\set{x}$ patří do právě jedné z přímek $p_i$
- $|X|=|\set{x}|+|p_1\setminus\set{x}|+|p_2\setminus\set{x}|+\dots+|p_{n+1}\setminus\set{x}|=$
- $=1+(n+1)\cdot n=n^2+n+1$
třetí bod
- graf incidence – bipartitní graf, nahoře přímky, dole body
- každý vrchol dolní partity má stupeň $n+1$
- každý vrchol horní partity má stupeň $n+1$
- celá dolní partita má $n^2+n+1$ vrcholů
- to už stačí
- počítání dvěma způsoby
  - počítáme počet dvojic $(x,p)\in X\times \mathcal P$ $(x, p) \in X \times P$ takových, že $x\in p$ $x \in p$
    - těch je $|X|\cdot(n+1)=(n^2+n+1)(n+1)$
    - je jich taky $|\mathcal P|\cdot(n+1)$
    - tudíž $(n^2+n+1)(n+1)=|\mathcal P|\cdot(n+1)$
    - proto $|\mathcal P|=(n^2+n+1)$

Projektivní roviny

df: mějme projektivní rovinu $(X,\mathcal P)$ ; potom duální projektivní rovina k $(X,\mathcal P)$ je hypergraf $(X^*,\mathcal P^*)$ , kde

$X^*=\mathcal P$ ,
pro $x\in X$ definujme $x^*:=\set{p\in\mathcal P:x\in p}$
$\mathcal P^*=\set{x^*:x\in X}$

Projektivní roviny

tvrzení: $(X^*,\mathcal P^*)$ je projektivní rovina

důkaz viz záznam
idea: první dva axiomy stačí prohodit
A3: nejvýše dvě přímky z Č* (množina 4 přímek) procházejí skrz x
- existuje množina 4 přímek takových, že žádné tři z nich neprocházejí jedním bodem
- máme 4 body z A3 v původní projektivní rovině – označíme $a,b,c,d$
- zvolíme přímky $\overline{ab},\overline{bc},\overline{cd}$ $\overline{ab}, \overline{b c}, \overline{c d}$
  - průnik prvních dvou je $b$
  - průnik druhých dvou je $c$
  - společný bod nemají

Projektivní roviny

konstrukce KPR řádu $n\in \mathbb N$

nechť $T$ je konečné těleso s $n$ prvky (tedy $n$ musí být kladná celá mocnina prvočísla), uvažujme vektorový prostor $V=T^3=\set{(x,y,z):x,y,z\in T}$ , $|V|=n^3$
nechť $X$ je mmnožina podprostorů dimenze 1 ve $V$
$|X|=\frac{n^3-1}{n-1}$ $∣ X ∣ = \frac{n ^{3} - 1}{n - 1}$
- protože máme $n^3-1$ nenulových vektorů, každý patří do jednoho podprostoru dimenze 1
- podprostor dimenze 1 má $n-1$ nenulových vektorů
$|X|=\frac{n^3-1}{n-1}=n^2+n+1$
pro každý podprostor $p\subseteq V$ dimenze 2 definuji $\tilde{p}:=\set{x\in X: x\subseteq p}$
$\mathcal P=\set{\tilde p:p\text{ je podprostor V dimenze 2}}$
$|\mathcal P|=|X|$ , protože podprostor dimenze 2 je ortogonálním doplňkem podprostoru dimenze 1 a protože existuje bijekce mezi podprostory a jejich ortogonálními doplňky
$(X,\mathcal P)$ $(X, P)$ je projektivní rovina
- důkaz jednoduchý, viz záznam

Toky v sítích

tokovou síť tvoří

$V$ … množina vrcholů
$E$ … množina orientovaných hran, $E\subseteq V\times V$
$z\in V$ … zdroj
$s\in V\setminus\set{z}$ … spotřebič / stok
$c:E\to [0,+\infty)$ … $c(e)$ je kapacita hrany $e$

Toky v sítích

tok v síti $(V,E,z,s,c)$ je funkce $f:E\to[0,+\infty)$ splňující

$\forall e\in E:0\leq f(e)\leq c(e)$
$\forall x\in V\setminus \set{z,s}:$ součet toků do vrcholu $x$ se rovná součtu toků z vrcholu (formálně pomocí sum) … Kirchhoffův zákon

Toky v sítích

pro vrchol $x\in V$ :

$\text{In}(x):=\set{(y,x)\in E}$
$\text{Out}(x):=\set{(x,y)\in E}$

Toky v sítích

pro $A\subseteq V$ :

$\text{In}(A):=\set{(u,v)\in E;\,u\notin A,\, v\in A}$
$\text{Out}(A):=\set{(u,v)\in E;\,u\in A,\, v\notin A}$

Toky v sítích

fakt: v každé tokové síti existuje maximální tok

poznámka: obecně na přednášce uvažujeme konečné tokové sítě, grafy apod.
idea důkazu: mějme síť, očíslujme hrany (od $1$ do $m$ ), tok $f$ reprezentujme jako uspořádanou $m$ -tici hodnot → množina všech toků je uzavřená a omezená podmnožina $\mathbb R^m$ , je tedy kompaktní; funkce, která toku $f$ přiřadí $w(f)$ , je spojitá; víme z analýzy, že spojitá funkce na kompaktní množině nabývá maxima

Toky v sítích

důkaz

víme
- $w(f)=f[\text{Out}(z)]-f[\text{In}(z)]$
- $\forall x\in A\setminus\set{z}:0=f[\text{Out}(x)]-f[\text{In}(x)]$
sečteme rovnosti: $w(f)=\sum_{x\in A}f[\text{Out}(x)]-\sum_{x\in A}f[\text{In}(x)]$
$\sum_{x\in A}f[\text{Out}(x)]$ … sčítá všechny hrany, které vycházejí ze všech vrcholů $A$ – tyto hrany jsou dvou typů, buď končí opět v $A$ , nebo končí mimo $A$
$E_A:=\set{(u,v)\in E:u\in A,\,v\in A}=E\cap(A×A)$ (hrany, které začínají v $A$ a končí v $A$ )
$w(f)=f[\text{Out}(A)]+f[E_A]-(f[\text{In}(A)]+f[E_A])$

Toky v sítích

df: nechť $f$ je tok v síti $(V,E,z,s,c)$ ; nenasycená cesta pro $f$ je neorientovaná cesta $x_1e_1x_2e_2\dots x_ke_kx_{k+1}$ , kde $\forall i:$ buď $e_i=(x_i,x_{i+1})$ ( $e_i$ je dopředná hrana), nebo $e_i=(x_{i+1},x_i)$ ( $e_i$ je zpětná hrana) a navíc platí

pro každou dopřednou hranu $e_i$ platí $f(e_i)\lt c(e_i)$
pro každou zpětnou hranu $e_i$ platí $f(e_i)\gt 0$

Toky v sítích

důkaz, že $w(f)\leq c(R)$

definujme $A:=$ vrcholy $x\in V$ takové, že existuje orientovaná cesta ze $z$ do $x$ nepoužívající hrany $R$
$z\in A$ , $s\notin A$ , $\text{Out}(A)\subseteq R$
$w(f)=f[\text{Out}(A)]-f[\text{In}(A)]\leq f[\text{Out}(a)]\leq c(\text{Out}(A)) \leq c(R)$

Toky v sítích

věta: nechť $f$ je tok v síti; potom následující tvrzení ekvivalentní

$f$ je maximální
$f$ nemá zlepšující cestu
existuje řez $R$ takový, že $w(f)=c(R)$

Toky v sítích

dk

$1\implies 2:$ jednoduše obměnou
$3\implies 1:$ pro libovolný řez $R'$ a libovolný tok $f'$ platí, že $w(f')\leq c(R')$ ; kdyby $f$ nebyl maximální, tak existuje $f^+$ tok splňující $w(f^+)\gt w(f)$ , potom pro každý řez $R$ platí, že $c(R)\geq w(f^+)\gt w(f)$ , tedy neexistuje žádný řez $R$ splňující $c(R)=w(f)$
$2\implies 3$ $2 ⟹ 3$
- nechť $f$ je tok, který nemá zlepšující cestu
- definujme množinu $A:=\set{x\in V,\,\text{ze }z\text{ do }x\text{ vede nenasycená cesta}}$
- zjevně $z\in A,\,s\notin A$
- definujme $R:=\text{Out}(A)=\set{uv\in E,\,u\in A,\,v\notin A}$
- všimněme si $\forall e\in\text{Out}(A):f(e)=c(e)$
- $\forall e'\in\text{In}(A):f(e')=0$
- z lemmatu výše víme, že pro $A\subseteq V$ , kde $z\in A,\,s\notin A$ , platí $w(f)=\underbrace{f[\text{Out}(A)]}_{c(\text{Out}(A))=c(R)}-\underbrace{f[\text{In}(A)]}_{0}=c(R)\quad\square$

Toky v sítích

dk:

nechť $G=(V,E)$ je bipartitní graf s partitami $A,B$
vytvořme tokovou síť $(V\cup\set{z,s},E^+,z,s,c)$ , kde $E^+=\set{zx\mid x\in A}\cup\set{ys\mid y\in B}\cup \set{xy\mid \set{x,y}\in E\land x\in A\land y\in B}$ (nestačí použít $E$ , protože orientujeme hrany z ) a $c(zx)=c(ys)=1$ pro $x\in A,\,y\in B$ a $c(xy)=|A|+|B|+1$ (prakticky nekonečno)
nechť $C_\min$ je nejmenší vrcholové pokrytí v $G$ , $M_\max$ největší párování v $G$
jistě $|M_\max|\leq |C_\min|$
nechť $f$ je maximální tok v té síti a $R$ minimální řez
dle minimaxové věty $w(f)=c(R)$
BÚNO $f$ má celočíselné hodnoty
definujme $M_f:=\set{\set{x,y}\in E:f(xy)\gt 0}$ $M_{f} := {{x, y} \in E : f (x y) > 0}$
- jistě $M_f$ párování v $G$ , navíc $|M_f|=w(f)$
definujme $C_R:=\set{x\in A:zx\in R}\cup\set{y\in B:ys\in R}$ $C_{R} := {x \in A : z x \in R} \cup {y \in B : ys \in R}$
- pozorování: $R$ neobsahuje žádnou hranu z $A$ do $B$
- jistě $C_R$ je vrcholové pokrytí $G$
- kdyby $C_R$ nebylo pokrytí, tak existuje nepokrytá hrana $\set{x,y}\in E$ , potom cesta $z\to x\to y\to s$ je ve sporu s tím, že $R$ je řez
- navíc $|C_R|=|R|=c(R)$
- máme $|C_\min|\leq |C_R|=c(R)=w(f)=|M_f|\leq |M_\max|\leq |C_\min|$

Toky v sítích

dk:

$\implies$ $⟹$
- pokud existuje párování velikosti $|A|$ , tak pro každou $X\subseteq A$ existuje $|X|$ vrcholů spárovaných s $X$ , ty patří do $N(X)$ , tedy $|N(X)|\geq |X|$
$\impliedby$ $⟸$
- nechť $M$ je největší párování v $G$
- pro spor nechť $|M|\lt|A|$
- dle K-E věty: existuje pokrytí $C$ , kde $|C|=|M|\lt |A|$
- $C_A:= C\cap A$
- $C_B:=C\cap B$
- $X:=A\setminus C_A$
- zjistím, že $N(X)\subseteq C_B$
- navíc $|X|=|A|-|C_A|\gt |C_B|\geq |N(x)|$
- to je spor s Hallovou podmínkou $\quad\square$

Toky v sítích

další verze Hallovy věty

df: systém různých reprezentantů (SRR) v hypergrafu $H=(V,E)$ $H = (V, E)$ je funkce $r:E\to V$ $r : E \to V$ taková, že
- $\forall e\in E: r(e)\in e$
- $\forall e,v\in E:e\neq f\implies r(e)\neq r(f)$ … tj. $r$ je prostá
$r(e)$ … „reprezentant hypergrany $e$ “
analogie s předsedy spolků
jakmile uvnitř hypergrafu je množina čtyř hyperhran, které ve svém sjednocení mají tři vrcholy, tak nemůžu najít systém různých reprezentantů
- platí to obecně pro množinu $k$ hyperhran – když budou mít ve sjednocení méně než $k$ vrcholů, tak nenajdu SRR
- implikace platí i obráceně, lze vyslovit jako větu
Hallova věta (hypergrafová verze): Hypergraf $H=(V,E)$ má SRR, právě když $\forall F\subseteq E:\left|\bigcup_{e\in F} e\right|\geq |F|$
důkaz
- nechť $H=(V,E)$ je hypergraf, nechť $I_H$ je jeho graf incidence
- pozorování: $H$ má SRR $\iff$ $I_H$ má párování velikosti $|E|$
- pozorování: Hallova podmínka pro $H$ : $\forall F\subseteq E: \left|\bigcup_{e\in F}e\right|\geq |F|\iff$ bipartitní Hallova podmínka pro $I_H$ a partitu $E$

Toky v sítích

df

pro $F\subseteq E:G-F:=(V,E\setminus F)$
$F\subseteq E$ je hranový řez v $G$ , pokud $G-F$ je nesouvislý
$G$ je hranově $k$ -souvislý, pokud neobsahuje žádný hranový řez velikosti menší než $k$

Toky v sítích

důkaz

$\implies:$ pokud máme $k$ hranově disjunktních cest z $x$ do $y$ , tak každý hranový $xy$ -řez musí obsahovat aspoň jednu hranu z každé té cesty
$\impliedby$ $⟸$
- nechť $G$ neobsahuje hranový $xy$ -řez velikosti menší než $k$
- vyrobíme tokovou síť $(V,\vec E,x,y,c)$ , kde $\vec E=\set{uv,vu\mid \set{u,v}\in E},\; \forall e\in \vec E: c(e)=1$
- pozorování: v té síti není žádný řez velikosti menší než $k$
- tedy v té síti existuje tok velikosti aspoň $k$
- nechť $f$ je celočíselný maximální tok
- navíc mezi všemi celočíselnými maximální toky volme $f$ tak, aby množina $\underbrace{\set{e\in\vec E:f(e)=1}}_{S(f)}$ byla co nejmenší
- pozorování: $S(f)$ neobsahuje žádný orientovaný cyklus jinak spor s minimalitou $S(f)$
- pomocí $S(f)$ $S (f)$ vyrobím k hranově disjunktních cest z $x$ $x$ do $y$ $y$ takto:
  - opakuj $k$ $k$ -krát
    - začni v $x$
    - jdi po hranách z $S(f)$ $S (f)$ , dokud nedojdeš do $y$ $y$
      - tenhle krok bude konečný, protože $S(f)$ neobsahuje orientované cykly
    - použité hrany odstraň z $S(f)$

Toky v sítích

dk:

$\implies$ zřejmá
$\impliedby$ $⟸$
- nechť $G$ nemá vrcholový $xy$ -řez velikosti $\lt k$
- vyrobíme síť $\mathcal S$ $S$ takto
  - za každý vrchol $u\in V$ dáme do $\mathcal S$ dva vrcholy $u^+,u^-$ a hranu $u^+u^-$ s kapacitou 1
  - za každou hranu $\set{u,v}\in E$ dáme do $\mathcal S$ dvě orientované hrany $u^-v^+$ a $v^-u^+$ s kapacitami " $\infty$ "
  - zdroj: $x^-$ , stok: $y^+$
- tvrdím, že $\mathcal S$ $S$ nemá řez kapacity $c\lt k$ $c < k$
  - sporem: nechť takový řez existuje
  - potom všechny jeho hrany jsou tvaru $u^+u^-$ pro nějaké $u\in V$ a odpovídající vrcholy v $G$ tvoří vrcholový $xy$ -řez velikosti $c\lt k$ , což je spor
- podle minimaxové věty o toku a řezu v $\mathcal S$ existuje tok velikosti $\geq k$ , BÚNO je ten tok celočíselný, říkejme mu $f$
- z existence takového $f$ plyne, že $\mathcal S$ obsahuje $k$ hranově disjunktních cest z $x^-$ do $y^+$ (viz hranová verze), označme je $\vec P_1,\dots,\vec P_k$
- ty cesty $\vec P_1,\dots,\vec P_k$ jsou i vnitřně vrcholově disjunktní, protože každá cesta (orientovaná) z $x^-$ do $y^+$ v $\mathcal S$ , která obsahuje vrchol $u^+$ nebo $u^-$ pro nějaké $u\in V\setminus\set{x,y}$ , musí obsahovat i hranu $u^+u^-$
- když v cestách $\vec P_1,\dots,\vec P_k$ nahradíme každou hranu tvaru $u^+u^-$ jedním vrcholem $u$ , tak dostaneme $k$ VVD cest z $x$ do $y$ v $G\quad\square$

Toky v sítích

dk:

nechť $A$ je nejmenší vrcholový řez v $G^-$
potom $k_v(G^-)=|A|$
chceme $k_v(G)\leq k_v(G^-)+1=|A|+1$
rozlišme případy
- pokud existuje komponenta $G^--A$ , která neobsahuje $x$ ani $y$ , tak $A$ je vrcholový řez v $G$ , tedy $k_v(G)\leq |A|$
- jinak má $G^--A$ 2 komponenty, jedna obsahuje $x$ (říkejme jí $G^-_x$ ), druhá $y$ ( $=: G_y^-$ )
- (zbytek viz záznam)

Toky v sítích

dk:

pro $K_n$ věta zjevně platí (jedna cesta je přímá, další vždy přes jiný vrchol, těch je $n-2$ )
nechť $G$ $G$ není úplný (byť by tahle větev důkazu fungovala i pro $K_n$ $K_{n}$ )
- $\impliedby:$ mezi každými dvěma vrchol je $k$ VVD cest $\implies$ G má $\geq k+1$ vrcholů, žádný řez velikosti $\lt k\implies G$ je $k$ -souvislý
- $\implies:$ $⟹ :$ nechť $x,y$ $x, y$ jsou různé vrcholy; případy
  - $\set{x,y}\notin E$ … viz $xy$ -verze M. věty
  - $\set{x,y}\in E:$ ${x, y} \in E :$ nechť $G^-:=(V,E\setminus\set e)$ $G^{-} := (V, E ∖ {e})$
    - podle lemmatu: $k_v(G^-)\geq k-1$
    - podle $xy$ -verze M. věty pro $G^-$ existuje $k-1$ VVD cest $x\to y$
    - přidám k nim hranu $e$ a mám $k$ VVD cest $x\to y\quad\square$

Toky v sítích

df: přidání ucha ke grafu $G=(V,E)$ je tato operace

zvol dva různé vrcholy $x,y\in V$
pro $d\geq 0$ přidej vrcholy $z_1,z_2,\dots,z_d$
přidej hranu cesty $xz_1z_2\dots z_dy$

Toky v sítích

důkaz

$\impliedby$ kružnice je 2-souvislá a přidání ucha nevytvoří řez velikosti $\leq 1$
$\implies$ $⟹$
- nechť $G=(V,E)$ je 2-souvislý, nechť $C$ je libovolná kružnice v $G$ , nechť $G_\max=(V_\max,E_\max)$ je největší podgraf $G$ , který se dá vyrobit přidáváním uší k $C$
- tvrdíme, že $G_\max=G$
- kdyby ne:
  - $V_\max=V,\,E_\max\subsetneq E:$ spor s maximalitou $G_\max$ , protože přidání hrany je přidání ucha
  - $V_\max\subsetneq V:G$ je souvislý, tak $\exists e=\set{xy}\in E$ taková, že $x\in V_\max$ a $y\notin V_\max$
  - $G-x$ je souvislý, protože $G$ je 2-souvislý
  - takže bude existovat ještě další cesta do $V_\max$
  - tato cesta + hrana $xy$ = další ucho

Cayleyho vzorec

věta (Cayleyho vzorec, Borchardt)

$s_n=n^{n-2}$

Cayleyho vzorec

důkaz

nebudu počítat stromy, ale kořenové stromy
df: kořenový strom je strom, ve kterém se jeden vrchol určil jako kořen a všechny hrany se zorientovaly směrem ke kořeni
$k_n:=$ počet kořenových stromů
pozorování: $k_n=n\cdot s_n$
pozorování: pokud ve stromě zorientuji hrany tak, aby z každého vrcholu odcházela nejvýš jedna hrana, tak potom existuje právě jeden vrchol („kořen“), z něhož žádná hrana neodchází, a navíc všechny hrany jsou orientované směrem ke kořeni
df: povykos (postup vytváření kořenového stromu) je posloupnost $n-1$ orientovaných hran $(e_1,e_2,\dots,e_{n-1})$ na vrcholech $[n]$ taková, že $([n],\set{e_1,\dots,e_{n-1}})$ je kořenový strom
$p_n:=$ počet povykosů
pozorování: $p_n=(n-1)!\cdot k_n$
pozorování (pravidla): posloupnost orientovaných hran $(e_1,e_2,\dots,e_{n-1})$ $(e_{1}, e_{2}, \dots, e_{n - 1})$ je povykos $\iff\forall k\in[n-1]:$ $⟺ \forall k \in [n - 1] :$
- hrana $e_k$ spojuje vrcholy z různých komponent grafu tvořeného hranami $e_1,\dots,e_{k-1}$
- hrana $e_k$ vychází z vrcholu, z něhož nevychází žádná z hran $e_1,\dots,e_{k-1}$
chci vyrobit povykos $(e_1,\dots,e_{n-1})$ $(e_{1}, \dots, e_{n - 1})$
- mám $n\cdot (n-1)$ $n \cdot (n - 1)$ možností, jak zvolit $e_1$ $e_{1}$
  - vybírám dva vrcholy, mezi kterými povedu hranu
- mám $n\cdot (n-2)$ $n \cdot (n - 2)$ možností, jak zvolit $e_2$ $e_{2}$ , když už znám $e_1$ $e_{1}$
  - mám $n$ možností, jak zvolit konec hrany
  - začátek hrany musí být v jiné komponentě než konec
  - je tam $n-2$ komponent, které můžu zvolit (dohromady je komponent $n-1$ , z toho jednu zvolit nemůžu)
  - v každé komponentě je „kořen komponenty“ (vrchol, z nějž žádná hrana nevychází)
  - hrana musí nutně začínat v „kořeni komponenty“ (podle druhého pravidla)
  - tedy mám $n-2$ možností, jak zvolit začátek hrany
- pokud už jsem vybral $e_1,\dots,e_{k-1}$ $e_{1}, \dots, e_{k - 1}$ v souladu s oběma pravidly, tak mám $n\cdot (n-k)$ $n \cdot (n - k)$ možností, jak vybrat $e_k$ $e_{k}$
  - $n$ … vyberu konec $e_k$
  - $n-k$ … vyberu začátek v kořeni nějaké komponenty neobsahující konec $e_k$
  - $p_n=n\cdot(n-1)\cdot n\cdot(n-2)\cdot\ldots\cdot n\cdot 1=$
  - $=\prod_{k=1}^{n-1}n(n-k)=n^{n-1}(n-1)!$
  - $k_n=\frac{p_n}{(n-1!)}=n^{n-1}$
  - $s_n=\frac{k_n}{n}=n^{n-2}\quad\square$

Počítání dvěma způsoby

příklad: fakulta má 1000 studujících, 50 předmětů, každý studující má zapsáno $\geq 10$ předmětů; dokažte, že existuje předmět, který má zapsáno $\geq 200$ lidí

řešení: sporem, nechť každý předmět má zapsáno $\lt 200$ lidí
počítejme počet dvojic $(x,y)$ $(x, y)$ , kde $x$ $x$ je studující, $y$ $y$ je předmět, $x$ $x$ má zapsán předmět $y$ $y$ , dvěma způsoby
- první způsob: těch dvojic je $\geq 1000\cdot 10$
- druhý způsob: těch dvojic je $\lt 50\cdot 200$
to je spor

Počítání dvěma způsoby

značení

$\mathcal P([n])$ … množina všech podmnožin množiny $[n]$
${[n]\choose k}$ … množina všech $k$ -prvkových podmnožin $[n]$

Počítání dvěma způsoby

důkaz

antiřetězec velikosti ${n\choose\lfloor n/2\rfloor}$ je např. ${[n]\choose\lfloor n/2\rfloor}$
dokažme, že neexistuje větší antiřetězec
- nechť $\mathcal A$ je aniřetězec, označme $\mathcal A=\set{A_1,A_2,\dots,A_k}$ , kde $k=|\mathcal A|$ , chceme $k\leq{n\choose\lfloor n/2\rfloor}$
- df: nasycený řetězec v $\mathcal P([n])$ je posloupnost $M_0,M_1,\dots,M_n\subseteq[n]$ , kde $M_0\subseteq M_1\subseteq\dots\subseteq M_n\subseteq [n]$ a $|M_i|=i$
- máme $n!$ $n!$ nasycených řetězců v $\mathcal P([n])$ $P ([n])$
  - začínám s prázdnou množinou, postupně do ní přidávám prvky
  - mám $n-i+1$ možností, jak do ní přidat $i$ -tý prvek
- každý nasycený řetězec obsahuje nejvýš jednu množinu $\mathcal A$
- počítejme dvěma způsoby dvojice $(A,\mathcal R)$ $(A, R)$ , kde $A\in\mathcal A$ $A \in A$ , $\mathcal R$ $R$ je nasycený řetězec, $A\in\mathcal R$ $A \in R$
  - první způsob: dvojic je $\leq n!$
  - druhý způsob: pro $A\in\mathcal A$ $A \in A$ mám $|A|!\cdot(n-|A|)!$ $∣ A ∣! \cdot (n - ∣ A ∣)!$ nasycených řetězců obsahujících $A$ $A$
    - mám množinu $A$
    - mám $|A|$ možností, který prvek z ní odeberu
    - postupně odebírám prvky, až se dostanu k prázdné množině → $|A|!$ možností
    - podobně $(n-|A|)!$ možností, jak dotvořit řetězec přidáváním prvků
  - $n!\geq\sum_{A\in\mathcal A}|A|!(n-|A|)!\implies 1\geq\sum_{A\in\mathcal A}\frac{|A|!(n-|A|)!}{n!}=\sum_{A\in\mathcal A}\frac1{n\over|A|}\geq\sum\frac1{n\choose\lfloor}$
  - pokračování viz záznam

Počítání dvěma způsoby

důkaz:

nechť $G=(V,E)$ je graf bez $C_4$ , $|V|=n$
označme $H$ počet dvojic $(x,\set{y,z})$ takových, že $x,y,z\in V$ , $y\neq z$ , $x$ je soused $y$ i $z$
počítejme $H$ $H$ dvěma způsoby
- pro dané $x\in V$ $x \in V$ mám přesně ${\deg x\choose 2}$ $(2 d e g x)$ možností, jak zvolit $y$ $y$ a $z$ $z$
  - tedy $H=\sum_{x\in V}{\deg x\choose 2}\geq\sum_{x\in V}\frac{(\deg x-1)^2}2$
- pro dané $\set{y,z}\in{V\choose 2}$ ${y, z} \in (2 V)$ existuje nejvýše jeden společný soused $x\in V$ $x \in V$ , jinak by $G$ $G$ obsahoval $C_4$ $C_{4}$
  - tedy $H\leq{n\choose 2}\leq\frac{n^2}2$
tedy $\frac{n^2}2\geq \sum_{x\in V}\frac{(\deg x-1)^2}2$
z toho plyne, že $n^2\geq \sum_{x\in V}{(\deg x-1)^2}$
chci $|E|=\frac 12\sum_{x\in V}\deg x\leq O(n^{3/2})$
uvažme funkci $f(x)=(x-1)^2$ , ta je konvexní, tedy pro každé $x_1,x_2,\dots,x_n\in\mathbb R: f(\frac{x_1+\dots+x_n}n)\leq\frac{f(x_1)+f(x_2)+\dots+f(x_n)}n$
tedy $n\geq\frac{\sum_{x\in V}{(\deg x-1)^2}}n\geq\left(\frac{\sum_{x\in V}\deg x}n-1\right)^2$ $n \geq \frac{\sum _{x \in V} ( d e g x - 1 ) ^{2}}{n} \geq (\frac{\sum _{x \in V} d e g x}{n} - 1)^{2}$
- počet hran je polovina ze součtu stupňů
$\sqrt n\geq\frac{2|E|}n-1$
$n^{3/2}\geq 2|E|-n$
$\frac12(n^{3/2}+n)\geq|E|\quad\square$

Počítání dvěma způsoby

poznámka: odhad je těsný

mějme incidenční graf konečné projektivní roviny řádu $k$
…

Ramseyovy věty

motivační tvrzeníčko: v každém grafu na 6 vrcholech existuje klika velikosti 3 nebo nezávislá množina velikosti 3

vezmu vrchol $v$ – zbývá pět vrcholů
$v$ je buď spojený se třemi vrcholy, nebo je nespojený se třemi vrcholy
pokud je spojený, dívám se na hrany mezi nimi

Ramseyovy věty

důkaz indukcí podle $k+\ell$

pozorování: $R(k,1)=1=R(1,\ell)$
pozorování: $R(k,2)=k=R(2,k)$
mějme $k\geq 3,\,l\geq 3$ , definujme $N:=R(k,\ell-1)+R(k-1,\ell)$
nechť máme dán graf $G$ na $N$ vrcholech
nechť $x$ je libovolný vrchol $G$
označme $S$ množinu sousedů vrcholu $x$ a $T=V\setminus (S\cup\set{x})$
protože $|S|+|T|=N-1=R(k,\ell-1)+R(k-1,\ell)-1$ , tak platí buď $|S|\geq R(k-1,\ell)$ , nebo $|T|\geq R(k,\ell-1)$
předpokládejme, že $|S|\geq R(k-1,\ell)$ , označme $G_S$ podgraf $G$ indukovaý $S$
tedy $G_S$ obsahuje kliku velikosti $k-1$ nebo nezávislou množinu velikosti $\ell$
pokud $G_S$ obsahuje nezávislou množinu velikosti $\ell$ , tak i $G$ ji obsahuje, hotovo
pokud $G_S$ obsahuje kliku velikosti $k-1$ , tak ta klika spolu s $x$ tvoří kliku velikosti $k$ v $G$ , hotovo
případ $|T|\geq R(k,\ell-1)$ je analogický
$V(G)=S\cup T\cup\set{x}$

Ramseyovy věty

věta (vícebarevná verze Ramseyovy věty): $\forall b\in\mathbb N\;\forall m\in\mathbb N\;\exists N\in\mathbb N\;\forall$ obarvení hran $K_N$ pomocí $b$ barev existuje množina $m$ vrcholů taková, že všechny hrany mezi nimi mají stejnou barvu

$R^*_b(m)$ … nejmenší $N$ s touto vlastností

Ramseyovy věty

důkaz

postupujme indukcí podle $b$
pro $b=1: R_1^*(m)=m$
pro $b=2:R^*_2(m)=R(m,m)$
nechť $b\gt 2$ $b > 2$
- nechť $N=R(m,R_{b-1}^*(m))$
- mějme obarvení $K_N$ pomocí $b$ barev
- nechť ty barvy jsou 1) modrá a 2) $b-1$ odstínů červené
- Ramseyova věta pro 2 barvy říká, že v tom obarvení buď existuje modrá klika velikosti $m$ (jsem hotov), nebo existuje klika $X$ velikosti $R^*_{b-1}(m)$ taková, že všechny barvy hran mezi vrcholy $X$ jsou odstíny červené
- $X$ indukuje úplný graf na $R^*_{b-1}$ , jehož hrany jsou obarveny pomocí $b-1$ barev, tedy v něm je jednobarevná klika velikosti $m$ $\square$

Ramseyovy věty

značení

${X\choose p}$ … množina $p$ -prvkových podmnožin $X$
$K_N^{(p)}$ $K_{N}^{(p)}$ … $p$ $p$ -uniformní úplný hypergraf, což je hypergraf $([N],{[N]\choose p})$ $([N], (p [ N ]))$
- tedy $K_N=K_N^{(2)}$

Ramseyovy věty

$p=1$

pro dané $b,m$ stačí $N=b(m-1)+1$
princip holubníku

Ramseyovy věty

důkaz

zakořeňme $T$ ve vrcholu $x_0$
indukcí definujme posloupnost vrcholů $x_0,x_1,x_2,\dots$ tak, že $x_0,x_1$ tvoří cestu a pro $\forall i\in\mathbb N_0:$ podstrom zakořeněný v $x_i$ má nekonečně mnoho vrcholů
už máme $x_0$
nechť už máme $x_0,x_1,\dots,x_n$ , nechť $y_1,y_2,\dots,y_k$ jsou děti $x_n$
aspoň jeden vrchol $y_i$ je kořenem nekonečného podstromu
tedy definujeme $x_{n+1}:=y_i$
posloupnost $x_0,x_1,x_2,\dots$ tvoí nekonečnou cestu v $T$

Ramseyovy věty

důkaz

nechť neplatí konečná Ramseyova věta, tedy $\exists p\;\exists b\;\exists m\;\forall N\;\exists\,b$ -obarvení $K_N^{(p)}$ neobsahující jednobarevnou podmnožinu velikosti $m$
řeknu, že $b$ -obarvení $\beta$ hypergrafu $K_N^{(p)}$ je záludné, pokud v něm neexistuje jednobarevná podmnožina $[N]$ velikosti $m$
$Z_N$ … množina záludných obarvení $K_N^{(p)}$
řeknu, že $b$ -obarvení $\gamma\in Z_{N+1}$ rozšiřuje $b$ -obarvení $\beta\in Z_N$ , pokud pro každou $h\in{[N]\choose p}$ platí $\gamma(h)=\beta(h)$
pozorování: každé $\gamma\in Z_{n+1}$ rozšiřuje právě jedno $\beta\in Z_N$
definujme strom $T$ na vrcholech $Z_1\cup Z_2\cup\dots=\bigcup_{N=1}^\infty Z_N$
$\set{\beta,\gamma}\in E(T)\iff\gamma$ rozšiřuje $\beta$ nebo naopak
v tom stromě existuje nekonečná cesta $\beta_1,\beta_2,\beta_3,\dots$ , kde $\beta_N\in Z_N$ (podle Kőnigova lemmatu)
definujme obarvení $\beta:{\mathbb N\choose p}\to[b]$ takto: nechť máme dánu množinu $h\in{\mathbb N\choose p}$ , volme $N\in\mathbb N$ takové, že $h\subseteq [N]$ a definujme $\beta(h):=\beta_N(h)$
tvrdím, že $\beta$ je záludné obarvení pro $K_\infty^{(p)}$
kdyby ne, tak $\beta$ má nějakou jednobarevnou $m$ -prvkovou množinu $X\subseteq\mathbb N$
volme $N$ tak, že $X\subseteq[N]$
potom $\beta$ obarví ${X\choose p}$ stejně jako $\beta_N$ , ale $\beta_N$ je záludné pro $K_N^{(p)}$ , tedy $X$ v něm není jednobarevná
tedy $\beta$ je záludné pro $K_\infty^{(p)}$ , a tedy nekonečná Ramseyova věta neplatí $\quad\square$

Samoopravné kódy

naše omezení

nad abecedou $\mathbb Z_2$
informace je rozdělená na slova pevné délky $k$ , každé se zakóduje do slova délky $n$
chyby při přenosu nemění počet symbolů

Samoopravné kódy

příklady

trojnásobné opakování
- 0 → 000
- 1 → 111
- dekódování: 011 → 111 → 1
kontrola parity
- když posílám 3 bity, tak 4. se rovná XORu těch prvních tří (tedy součtu nad $\mathbb Z_2$ )

Samoopravné kódy

pozorování

$\Vert x\Vert=d(x,0)$
$d(x,y)=\Vert x\oplus y\Vert$

Samoopravné kódy

např.

$C_1=\set{000,111}$ je $(3,1,3)$ -kód
$C_2=\set{x\in\mathbb Z_2^4;\Vert x\Vert\text{ je sudá}}$ je $(4,3,2)$ -kód … tohle odpovídá kontrole parity

Samoopravné kódy

pro $C_1:$

$(0)(111)=(000)$
$(1)(111)=(111)$

Samoopravné kódy

dk

uvažujeme zobrazení $f:\mathbb Z_2^k\to \mathbb Z_2^n$ definované $f(x)=xG$
stačí ověřit
1. $\forall x\in\mathbb Z_2^k:f(x)\in C$
2. $f$ je prosté
ověřme 1)
- nechť $r_1,\dots,r_k$ jsou řádky $G$ , tedy $r_1,\dots,r_k\in C$
- potom pro každé $x=(x_1,\dots,x_k)$ platí $xG=x_1r_1\oplus x_2r_2\oplus\dots\oplus x_kr_k$ , což je lineární kombinace prvků $C$ , tedy prvek $C$
ověřme 2)
- kdyby $\exists x\neq x'\in\mathbb Z_2^k:f(x)=f(x')$
- tak $xG=x'G\iff \underbrace{(x-x')}_{\neq 0}G=\underline 0$ , což nemůže nastat, protože řádky $G$ jsou lineárně nezávislé

Samoopravné kódy

fakt

pokud $C$ je podprostor dimenze $k$ , tak $C^\perp$ je podprostor dimenze $n-k$
$(C^\perp)^\perp=C$ , pokud $C$ je podprostor $\mathbb Z_2^n$

Samoopravné kódy

postup

máme $x\in\mathbb Z_2^{k}$
kódováním pomocí funkce $f$ dostaneme $y\in C\subseteq\mathbb Z_2^n$
přenosem dostaneme $\tilde y\in C$
dekódováním pomocí funkce $g$ dostaneme $\bar y\in C$
z $\bar y$ pomocí funkce $f^{-1}$ dostaneme $\bar x\in\mathbb Z_2^{k}$

Samoopravné kódy

příklad

$C_1=\set{000,111}$ , lineární $(3,1,3)$ -kód
$C_1^\perp=\set{000,110,101,011}$
$C_1$ má kontrolní matici např. ${110\choose 011}$

Samoopravné kódy

důkaz

nechť $r_1,r_2,\dots,r_{n-k}\in\mathbb Z_2^n$ jsou řádky $K$
potom $x\in C\iff x\in(C^\perp)^\perp\iff\forall y\in C^\perp:\braket{x,y}=0$ $\iff \forall i\in\set{1,\dots,n-k}:\braket{x,r_i}=0\iff Kx^T=\underline 0$

Samoopravné kódy

důsledky

$\Delta(C)\geq 2\iff K$ má všechny sloupce nenulové
$\Delta(C)\geq 3\iff K$ má všechny sloupce nenulové a navíc každé dva sloupce různé

Samoopravné kódy

navíc to $y\in H_r$ lze najít následujícím algoritmem

spočítej $K_rx^T=:s$
pokud $s=\underline 0$ , tak $x\in H_r$ , tedy $y:=x$
pokud $s\neq\underline 0$ , tak nechť $i\in\set{1,\dots,n}$ je takové, ž $i$ -tý sloupec $K_r$ je roven $s$ ; potom nechť $y$ je vektor, který vznikne z $x$ změnou $i$ -tého bitu

Samoopravné kódy

důkaz

nechť $C$ je $(n,k,d)$ -kód
definujme funkci $\psi:\mathbb Z_2^n\to\mathbb Z_2^{n-d+1}$
$\psi(x_1,\dots,x_n)=(x_1,\dots,x_{n-d+1})$
pro $x,y\in C$ , $x\neq y$ , tak $\psi(x)\neq\psi(y)$
tedy $|C|\leq 2^{n-d+1}$
tedy $k\leq n-d+1$ , tj. $k+d\leq n+1$
stručně: $d$ označuje počet bitů, ve kterých se dvě různá slova liší, takže když jich smažeme $d-1$ , tak se pořád budou lišit

Hurá, máš hotovo! 🎉
Pokud ti moje kartičky pomohly, můžeš mi koupit pivo.