slama.dev

Kombinatorika a Grafy I

poznámky · 2. 1. 2021 · 🇨🇿 · dostupné v PDF · [upravit]

• 1. přednáška
  • Odhady faktoriálu
  • Odhady binomických koeficientů
• 2. přednáška
  • Náhodné procházky
  • Generující funkce
  • Zobecněná binomická věta
• 3. přednáška
  • Fibonacciho čísla
  • Catalanova čísla
  • Konečné projektivní roviny
    • Počet bodů a přímek
• 4. přednáška
  • Dualita KPR
  • Konstrukce KPR
• 5. přednáška
  • Latinské čtverce
  • NOLČ $\iff$ KPR
• 6. přednáška
  • Počítání dvěma způsoby
  • Grafy bez $C_k$
  • Počítání koster
• 7. přednáška
  • Toky
    • max flow, min cut
    • Ford-Fulkerson
• 8. přednáška
  • Aplikace toků v sítích
    • Párování v bipartitním grafu
    • Systém reprezentantů
• 9. přednáška
  • Míra souvislosti neorientovaných grafu
• 10. přednáška
  • Lepení uší
  • Samoopravné kódy
• 11. přednáška
  • Jak nejefektivněji můžeme kódovat?
  • Lineární kódy
    • Duální kódy
    • Dekódování
    • Hammingovy kódy
• 12. přednáška
  • Dekódování Hammingova kódu
  • Perfektnost kódu
  • Hadamardův kód
  • Ramseyova teorie
• 13. přednáška
  • Ramseyovy vícebarevně věty
• Forma zkoušky
• Zdroje/materiály
• Poděkování

Úvodní informace

Tato stránka obsahuje moje poznámky z přednášky Martina Kouteckého z akademického roku 2020/2021 (MFF UK). Pokud by byla někde chyba/nejasnost, nebo byste rádi něco přidali, tak stránku můžete upravit pull requestem (případně mi dejte vědět na mail).

1. přednáška

Odhady faktoriálu

Věta (meh odhad): $$n^{n/2} \le n! \le \left(\frac{n + 1}{2}\right)^n$$

Důkaz ($\ge$): $$\begin{aligned} \left(n!\right)^2 &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n \cdot n \cdot (n - 1) \cdot \ldots \cdot 2 \cdot 1 \\ &= \prod_{i = 1}^{n} \left(i \cdot (n - i + 1)\right) \end{aligned}$$

Využijeme A-G nerovnost:

$$\begin{aligned} \sqrt{ab} &\le \frac{a + b}{2} \\ \sqrt{i (n + 1 - i)} &\le \frac{i + n + 1 - i}{2} = \frac{n + 1}{2} \end{aligned}$$

Dostáváme: $$n! = \prod_{i = 1}^{n} \sqrt{i \cdot (n - i + 1)}\le \left(\frac{n + 1}{2}\right)^n$$

Důkaz ($\le$): $n \le i (n - i + 1), \forall i \in [n]$:

• $i = 1$ platí
• $i = 2 \rightarrow$ jeden člen je vždy $\ge 2$, druhý $\ge n/2$

$$\begin{aligned} \left(n!\right)^2 &= \prod_{i = 1}^{n} i\left(n - i + 1\right) \ge \prod_{i = 1}^{n}n = n^n \\ n! &\ge n^{n/2} \end{aligned}$$

Věta (nice odhad): $$e\left(\frac{n}{e}\right)^n \le n! \le en \left(\frac{n}{e}\right)^n$$

Důkaz (indukcí):

• $n = 1$: $$1 \le e \cdot 1 \cdot \frac{1}{e}$$
• $n - 1 \rightarrow n$: $$\begin{aligned} n! = n \left(n - 1\right)! &\le^\mathrm{IP} en \left(n - 1\right) \left(\frac{n - 1}{e}\right)^{n - 1} \\ &= en \left(\frac{n}{e}\right)^n \left(\frac{e}{n}\right)^n \left(n - 1\right) \left(\frac{n - 1}{e}\right)^{n - 1} \\ &= en \left(\frac{n}{e}\right)^n \underbrace{\left(\frac{n - 1}{n}\right)^n e}_{\le 1} \end{aligned}$$

Důkaz, toho proč ten výraz $\le 1$:

$$\begin{aligned} \left(1 - \frac{1}{n}\right)^n e &\le \left(e^{-\frac{1}{n}}\right)^n e = e^{-1} e = 1 \qquad 1 + x \le e^x \end{aligned}$$

• pozn.: $a \le b \implies a = b c$ pro $c \le 1$, proto to vlastně děláme
• pro dolní mez postupujeme podobně, ale je potřeba indukční krok dokazovat pro $n \rightarrow n+1$, místo $n-1 \rightarrow n$.

Věta (Stirlingova formule): $$n! \cong \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$$

Odhady binomických koeficientů

(👀): pro malé $k << n \ldots \binom{n}{k} = \frac{n!}{(n - k)! k!} = \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1)}{k!} \le n^k$

Věta (hodně meh odhad): $$\frac{2^n}{n + 1} \le \binom{n}{\left\lfloor n/2 \right\rfloor} \le 2^n$$

Důkaz:

• součet všech čísel v řádku je $2^n$, tak jistě to největší nebude větší
• největší sčítanec je rovněž alespoň tak velký jako průměrný

Věta (nice odhad): $$\frac{2^{2m}}{2 \sqrt{m}} \le \binom{2m}{m} \le \frac{2^{2m}}{\sqrt{2m}}$$

Důkaz: Nejprve jedno kouzlo: $$\begin{aligned} P &= \frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2m - 1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2m} \\ &= \frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2m - 1)}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2m}\frac{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2m}{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2m}\\ &= \frac{(2m)!}{2^{2m} \left(m!\right)^2} = \frac{\binom{2m}{m}}{2^{2m}} \end{aligned}$$

Chceme tedy: $$\frac{1}{2 \sqrt{m}} \le P \le \frac{1}{\sqrt{2m}}$$

Pak ještě druhé kouzlo: $$\begin{aligned} \left(1 - \frac{1}{2^2}\right) \ldots \left(1 - \frac{1}{\left(2m\right)^2}\right) &= \left(\frac{1 \cdot 3}{2 \cdot 2}\right) \left(\frac{3 \cdot 5}{4 \cdot 4}\right) \ldots \left(\frac{(2m - 1)(2m + 1)}{\left(2m\right)^2}\right) \\ &= P^2 (2m + 1) < 1 \qquad //\ \text{součin věcí $<1$} \\ \end{aligned}$$

Máme tedy: $$\begin{aligned} P^2 &< \frac{1}{2m + 1} < \frac{1}{2m} \\ P &< \frac{1}{\sqrt{2m}} \\ \end{aligned}$$

Druhá strana analogicky (uvažujeme $\left(1 - \frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\ldots = \left(\frac{2 \cdot 4}{3^2}\right)\left(\frac{4 \cdot 6}{5^2}\right)\ldots = \frac{1}{2 \left(2m\right) P^2}$).

2. přednáška

Náhodné procházky

Definice (náhodná procházka): Náhodný proces, v každém kroku se panáček začínající v bodu $0$ posune ze své aktuální pozice doprava nebo doleva.

• kde bude po $n$ krocích?
• $\lim_{n \to \infty} \ldots$ že se po $n$ krocích vrátil (někdy v průběhu) do počátku?
• $\lim_{n \to \infty} \ldots$ $\mathbb{E}[\#\text{návratů do počátku}]$?
  • dokážeme, že jde k nekonečnu

Zadefinujeme si náhodnou veličinu $X = I_{S_2} + I_{S_4} + \ldots + I_{S_{2n}}$:

• $I_{S_{2n}}\ldots$ indikátor, že nastal jev „po $2n$ krocích jsem v počátku“
• $\mathbb{E}[X] = \mathbb{E}[\#\text{návratů do počátku}]$.
• $\Pr[\text{po $2n$ krocích jsem v počátku}] = \binom{2n}{n}/2^{2n}$.
  • nahoře jsou možnosti vyrovnaných počtů kroků doprava/doleva
  • dole jsou všechny scénáře pro $2n$ kroků

$$\frac{\binom{2n}{n}}{2^{2n}} \ge \frac{\frac{2^{2n}}{2 \sqrt{n}}}{2^{2n}} = \frac{1}{2 \sqrt{n}}$$

$$\begin{aligned} \mathbb{E}[X] &= \mathbb{E}\left[\sum_{i=1}^{\infty} I_{S_{2i}}\right]&& \\ &= \sum_{i=1}^{\infty} \mathbb{E}\left[I_{S_{2i}}\right]&&//\ \text{linearita střední hodnoty}\\ &= \sum_{i=1}^{\infty} \Pr\left[I_{S_{2i}}\right] &&//\ \text{střední hodnota indikátoru je pravděpodobnost}\\ &\ge \sum_{i=1}^{\infty} \frac{1}{2 \sqrt{i}} && //\ \text{použití odhadu výše; diverguje} \\ \end{aligned}$$

• zajímavost: ve $2D$ to také platí, ale ve $3D$ už ne (konverguje k nějakému konstantnímu číslu)!

Generující funkce

Definice (mocninná řada): je nekonečná řada tvaru $a(x) = a_0 + a_1x^1 + a_2x^2 + \ldots,$ kde $a_0, a_1 \ldots \in \mathbb{R}$.

Příklad: $a_0 = a_1 = \ldots = 1 \mapsto 1 +x + x^2 + \ldots$

• pro $|x| < 1$ řada konverguje k $\frac{1}{1 - x}$, můžeme tedy říct, že $(1, 1, \ldots) \approx \frac{1}{1 - x}$

Tvrzení: $(a_0, a_1, a_2, \ldots)$ reálná čísla. Předpoklad: pro nějaké $K$ t. ž. $|a_n| \le K^n$. Poté řada $a(x)$ pro každé $x \in \left(-\frac{1}{K}, \frac{1}{K}\right)$ konverguje (dává smysl). Funkce $a(x)$ je navíc jednoznačně určena hodnotami na okolí $0$.

Definice (vytvořující/generující funkce): nechť $\left(a_0, a_1, \ldots\right)$ je posloupnost reálných čísel. Vytvořující funkce této posloupnosti je mocninná řada $a(x) = \sum_{i = 0}^{\infty} a_i x^i$.

operace	řada	úprava
součet	$a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots$	$a(x) + b(x)$
násobek	$\alpha a_0, \alpha a_1, \alpha a_2, \ldots$	$\alpha a(x)$
posun doprava	$0, a_0, a_1, \ldots$	$xa(x)$
posun doleva	$a_1, a_2, a_3, \ldots$	$\frac{a(x) - a_0}{x}$
substituce $\alpha x$	$\alpha^0 a_0, \alpha^1 a_1, \alpha^2 a_2, \ldots$	$a(\alpha x)$
substituce $x^n$	$a_0, 0, \overset{n - 1}{\ldots}, 0, a_1, 0, \overset{n - 1}{\ldots}, 0, a_2, \ldots$	$a(x^n)$
derivace	$a_1, 2a_2, 3a_3, \ldots$	$a'(x)$
integrování	$0, a_1, a_2/2, a_3/3, \ldots$	$\int_{0}^{x} a(t) dt$
konvoluce	$a_n = \sum_{k = 0}^{n} a_k \cdot b_{n - k}$	$a(x) \cdot b(x)$

Zde je několik příkladů řad a výrazů, kterým odpovídají (hodí se v důkazech): $$\begin{aligned} \sum_{n=0}^{\infty} x^n &= (1, 1, 1, 1, \ldots) &= \frac{1}{1 - x} \\ \sum_{n=0}^{\infty} (ax)^n &= (a^0, a^1, a^2, a^3, \ldots) &= \frac{1}{1 - ax} \\ \sum_{n=0}^{\infty} (x^2)^n &= (1, 0, 1, 0, \ldots) &= \frac{1}{1 - x^2} \\ \sum_{n=0}^{\infty} (-1)^n x^n &= (1, -1, 1, -1\ldots) &= \frac{1}{1 + x} \\ \end{aligned}$$

Zobecněná binomická věta

Chceme binomickou větu zobecnit i pro reálné exponenty. K tomu potřebujeme definici kombinačního čísla, která se s reálnými kamarádí. Uděláme následující: $$r \in \mathbb{R}, k \in \mathbb{N} \qquad \binom{r}{k} = \frac{r \cdot (r - 1) \cdot (r - 2) \cdot \ldots \cdot (r - k + 1)}{k!}$$

• pro $r \in \mathbb{N}$ se shoduje s tím, co už známe
• pro $r \in \mathbb{R}$ opět máme klesající součin $k$ prvků, ale hodnoty jsou reálné

Věta (ZBV): nechť $x, y, r \in \mathbb{R}$ a $|x| > |y|$ (kvůli konvergenci). Pak ZBV je následující výraz: $$(x+y)^r = \sum_{k = 0}^{\infty} \binom{r}{k} x^{r-k}y^k$$

Příklad:

• pro $y = 1$ (a prohozením $x$ a $y$) dostáváme $$(1 + x)^r = \left(\binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots\right)$$
• speciálně pro $r = \frac{1}{2}$ dostáváme $$\sqrt{1+x} = 1 + \frac{1}{2}x - \frac{1}{8} x^2 + \frac{1}{16} x^3 + \ldots$$

Příklad: V krabici je $30$ červených, $40$ žlutých a $50$ zelených míčků. Kolika způsoby lze vybrat $70$?

$$\begin{aligned} &(1 + x + \ldots + x^{30})(1 + x + \ldots + x^{40})(1 + x + \ldots + x^{50}) =\\ &= \frac{1 - x^{31}}{1 - x} \frac{1 - x^{41}}{1 - x}\frac{1 - x^{51}}{1 - x} \qquad //\ \text{posuneme o $31$ míst a odečteme}\\ &= \frac{1}{\left(1 - x\right)^3} \left(1 - x^{31}\right)\left(1 - x^{41}\right)\left(1 - x^{51}\right) \\ &= \left(\binom{2}{2} + \binom{3}{2}x + \binom{4}{2}x^2 + \ldots\right) \left(1 - x^{31}\right)\left(1 - x^{41}\right)\left(1 - x^{51}\right) \\ &= 1 + \ldots + \left[\binom{72}{2} - \binom{72 - 31}{2} - \binom{72 - 41}{2} - \binom{72 - 51}{2}\right]x^{70} + \ldots\\ &= 1061 \end{aligned}$$

Kde poslední rovnost platí, protože:

• z posledních 3 závorek si vybereme $1$ a z první závorky koeficient u $70$
• ze druhé $x^{31}$ a z první koeficient u $72 - 31$
  • analogicky pro $41$ a $51$ ze třetí a čtvrté

3. přednáška

Fibonacciho čísla

Definice: $F_0 = 0, F_1 = 1, F_n = F_{n - 1} + F_{n - 2}, \forall n \ge 2$

• Fibonacciho mocninnou řadou rozumíme $F(x) = F_0 + F_1x + F_2x^2 + F_3x^3 + \ldots$

Funkce/pozice	0	1	2	3	4
$x F(x)$	$0$	$F_0$	$F_1$	$F_2$	$F_3$
$x^2 F(x)$	$0$	$0$	$F_0$	$F_1$	$F_2$
$x$	$0$	$1$	$0$	$0$	$0$
	$\Downarrow$	$\Downarrow$	$\Downarrow$	$\Downarrow$	$\Downarrow$
$F(x)$	$F_0$	$F_1$	$F_2$	$F_3$	$F_4$

Z funkcí výše vidíme, že $F(x) = x + xF(x) + x^2F(x)$. Algebraickou úpravou dostáváme: $$\begin{aligned} F(x) &= \frac{x}{1 - x - x^2} \\ &= \frac{x}{\left(1 - \frac{1 + \sqrt{5}}{2}x\right)\left(1 - \frac{1 - \sqrt{5}}{2}x\right)} \qquad //\ \text{algebra}\\ &= \frac{\frac{1}{\sqrt{5}}}{1 - \frac{1 + \sqrt{5}}{2}x} - \frac{\frac{1}{\sqrt{5}}}{1 - \frac{1 - \sqrt{5}}{2}x} \qquad //\ \text{parciální zlomky }\\ &= \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \frac{1 + \sqrt{5}}{2}x} - \frac{1}{1 - \frac{1 - \sqrt{5}}{2}x}\right) \qquad //\ \text{tvary $\frac{\pm 1}{1 - ax}$}\\ \end{aligned}$$

Pro daný koeficient vytvořující funkce tedy máme: $$\begin{aligned} F_n &= \frac{1}{\sqrt{5}} \left[\left(\frac{1 + \sqrt{5}}{2}\right)^n - \underbrace{\left(\frac{1 - \sqrt{5}}{2}\right)^n}_{\text{jde k $0$}}\right] \\ &= \left\lfloor \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n \right\rfloor \\ \end{aligned}$$

Catalanova čísla

• $b_n =$ počet binárních zakořeněných stromů na $n$ vrcholech
  • $b_n = \sum_{k = 0}^{n - 1} b_k \cdot b_{n - k - 1}$, rekurzíme se na obě části
  • jde si rozmyslet¹, že $b(x) = x \cdot b(x) \cdot b(x) + 1$
    • $x$ je tam kvůli posunu, aby vycházelo správně indexování (suma nejde do $n$)
    • $1$ je tam kvůli tomu, aby nultý člen správně vycházel

$$\begin{aligned} b(x) &= x \cdot b(x)^2 + 1 \\ b(x)_{1, 2} &= \frac{1 \pm \sqrt{1 - 4x}}{2x} \qquad //\ \text{$+$ nedává smysl, diverguje}^*\\ \\ b(x) &= \frac{1 - 1 - \sum_{k = 1}^{\infty}(-4)^k \binom{1/2}{k} x^k }{2x} \qquad //\ \sqrt{1 - 4k} \overset{\text{z. binom. v.}}{=} \sum_{k = 0}^{\infty} (-4)^k \binom{1/2}{k} x^k\\ &= -\frac{1}{2} \sum_{k = 1}^{\infty} (-4)^k \binom{1/2}{k} x^{k - 1}\\ \\ b_n &= -\frac{1}{2} (-4)^{n + 1} \binom{1/2}{n + 1}\qquad //\ \text{konkrétní koeficient}\\ &= \frac{1}{2} (-1)^{n} 2^{2n + 2} \frac{\frac{1}{2} \cdot \left(\frac{1}{2} - 1\right) \cdot \overset{n + 1}{\ldots} \cdot \left(\frac{1}{2} - n\right)}{\left(n + 1\right)!}\\ &= \frac{1}{2} (-1)^{n} 2^{2n + 2} \frac{\frac{1}{2} \cdot \left(-\frac{1}{2}\right) \cdot \overset{n + 1}{\ldots} \cdot \left(-\frac{2n - 1}{2}\right)}{\left(n + 1\right)!}\\ &= \frac{1}{2} 2^{2n + 2} \frac{\frac{1}{2} \cdot \frac{1}{2} \cdot \ldots \cdot \frac{2n - 1}{2}}{\left(n + 1\right)!} \qquad //\ \text{krácení záporných čísel}\\ &= 2^{n} \frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n - 1)}{(n + 1)!} \cdot \frac{n!}{n!} \qquad //\ \text{krácení $2$}\\ &= \frac{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n - 1)}{(n + 1) n!} \cdot \frac{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{n!} \qquad //\ \text{rozdistribuování $2$}\\ &= \frac{1}{n + 1} \frac{(2n)!}{\left(n!\right)^2} \\ &= \frac{1}{n + 1} \binom{2n}{n} \\ \end{aligned}$$

$*$: divergencí myslíme v rámci toho tvrzení o slušně vychovaných vytvořujících funkcí: funkce $\frac{1 + \sqrt{1 - 4x}}{2x}$ na okolí $0$ konverguje zleva a zprava k jiným hodnotám

Konečné projektivní roviny

Definice (KPR): Nechť $X$ je konečná množina, $\mathcal{P}$ systém podmnožin množiny $X$. $\left(X, \mathcal{P}\right)$ je KPR pokud:

1. Existuje $\mathcal{C} \subseteq X, |\mathcal{C}| = 4$ t. ž. $\forall P \in \mathcal{P}: |P \cap \mathcal{C}| \le 2$
   • „každá přímka obsahuje $\le 2$ body z $\mathcal{C}$“
2. $\forall P, Q \in \mathcal{P}, P \neq Q: \exists! x \in X$ t. ž. $P \cap Q = \left\{x\right\}$
   • „každé dvě přímky se protínají právě v $1$ bodě“
3. $\forall x, y \in X, x \neq y \exists! P \in \mathcal{P}$ t. ž. $x, y \in \mathcal{P}$
   • „každé dva body určují právě $1$ přímku“

• $x \in X$ je bod
• $P \in \mathcal{P}$ je přímka

Příklad (Fanova rovina):

Počet bodů a přímek

Tvrzení: „v KPR mají všechny přímky stejný počet bodů“

Pomocné tvrzení: $\forall P, P' \in \mathcal{P} \exists z \in X$, které neleží ani na jedné z nich.

Dokáže se přes to přes rozbor příkladů toho, jak vedou přímky přes $\mathcal{C}$:

• pokud nevedou přes všechny body z $\mathcal{C}$, pak máme vyhráno
• pokud vedou, tak existují dvě další přímky $P_1$ a $P_2$ vedoucí kolmo na naše přímky, jejich průnik je hledaný bod; původní přímky jím vést nemohou, protože pak by dvě přímky sdílely 2 body, což nelze
• $P_1 \neq P$, protože pak by $P$ obsahovala alespoň 3 body z $\mathcal{C}$. Podobně ostatní nerovnosti.

4. přednáška

Důkaz původního tvrzení: pro přímky $P$, $P'$ a bod $z$ (který nesdílí) budeme dělat bijekci tak, že budu tvořit přímky z bodu $z$ na body z $P$, které budou rovněž protínat body z $P'$.

Definice (řád KPR): řádem $(X, \mathcal{P})$ je $n = |P| - 1$ pro jakoukoliv $P \in \mathcal{P}$.

Tvrzení: nechť $(X, \mathcal{P})$ je KPR řádu $n$. Pak:

1. každým bodem prochází $n + 1$ přímek
2. $|X| = n^2 + n + 1$
3. $|\mathcal{P}| = n^2 + n + 1$

Důkaz: {:.rightFloatBox}

1. triviálně z definice.
2. viz. níže.
3. vychází z duality (viz. další kapitola).

Vezměme libovolné $x \in X$. Pak $\exists P \in \mathcal{P}: x \not\in P$, protože vezmeme-li body $a, b, c \in \mathcal{C}$, pak přímky $ab$ a $ac$ nemohou mít další společný bod než $a$ (došlo by ke sporu s některým z axiomů).

Poté stačí uvážit následující obrázek a spočítat body/přímky. Další bod už neexistuje, protože kdyby existoval, tak by jím musela procházet přímka z $x$ a ta by rovněž někde protínala $P$ (a nesplňovala tak axiomy).

Bodů na obrázku je $\overbrace{1}^{x} + \underbrace{\left(n + 1\right)}_{P_0 \ldots P_n}\overbrace{n}^{\text{body $P_i$, bez $x$}} = n^2 + n + 1$.

Dualita KPR

Definice (incidenční graf): nechť $(X, \mathcal{S})$ je množinový systém ($\mathcal{S} \subseteq 2^X$). Jeho incidenční graf je bipartitní graf $$\left(V = X \cup \mathcal{S}, E = \left\{(x, s) \in X \times \mathcal{S}\ |\ x \in s\right\}\right)$$

Definice (duál grafu): $(Y, \mathcal{T})$ je duál $(X, \mathcal{S})$ pokud $Y = \mathcal{S}$ a $\mathcal{T} = \left\{\left\{s \in \mathcal{S}\ |\ x \in s\right\}\ |\ x \in X\right\}$

• (👀): incidenční graf $(Y, \mathcal{T})$ je incidenční graf $(X, \mathcal{S})$ s prohozením stran

Příklad (duál Fanovy roviny):

Věta: duál KPR je KPR.

Důkaz: ověření axiomů v duálním světě:

1. $\exists \mathcal{C}$ čtveřice přímek t. ž. $\forall x \in X$ leží na nanejvýš $2$ přímkách z $\mathcal{C}$
   • stejné jako „žádné $3$ přímky z $\mathcal{C}$ nemají společný bod“
   • zvolím $\mathcal{C} = \left\{ab, cd, ad, bc\right\}$, což funguje (zkusit si rozkreslit)
2. $\forall x, y \in X, x \neq y: \exists! P \in \mathcal{P}$ t. ž. jimi prochází právě $1$ přímka
   • stejné jako původní axiom o přímkách
3. analogicky viz. ^

Důsledek: $(X, \mathcal{P})$ je řádu $n \implies |\mathcal{P}| = n^2 + n + 1$

• duál $(Y, \mathcal{T})$ je duál $(X, \mathcal{P})$, ten je stejného řádu a proto je i velikost $|\mathcal{P}| = n^2 + n + 1$

Konstrukce KPR

Pro KPR řádu $p^k$, $p$ prvočíslo vezmu algebraické těleso $\mathbb{K}$ řádu $n$ (příklad $\mathbb{K} = \mathbb{Z}_3$).

• $T = \mathbb{K}^3 \setminus \left(0, 0, 0\right)$
• na $T$ zavedu ekvivalenci $(x, y, t) \in T$ je ekvivalentní s $(\lambda x, \lambda y, \lambda t), \forall \lambda \in \mathbb{K} \setminus {0}$
• body $X$ jsou ekvivalenční třídy nad $T$
• reprezentanti: poslední nenulová složka je $1$
  • trojice tvaru $(x, y, 1), (x, 1, 0), (1, 0, 0)$
  • můžu si to dovolit, na reprezentanta převedu prostým pronásobením
  • počet je $n^2 + n + 1$, což sedí
• přímky $\mathcal{P}$: pro každou $(a, b, c) \in T$ definujeme přímku $P_{a, b, c}$ jako množinu bodů $(x, y, t)$ splňující $ax + by + ct = 0$
  • $\forall (x, y, t) \in T, \forall \lambda \neq 0: (x, y, t)$ splňuje $\iff (\lambda x, \lambda y, \lambda t)$ splňuje
  • $\forall (a, b, c) \in T, \forall \lambda$ fixuji $(x, y, t) \in T: ax + by + ct = 0 \iff \lambda ax + \lambda by + \lambda ct = 0 \implies$ přímky $P_{a, b, c} = P_{\lambda a, \lambda b, \lambda c} \implies |\mathcal{P}| = |X|$ a mohu si opět zvolit reprezentanty

Ověření axiomů:

1. $\mathcal{C} = \left\{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)\right\}$
   • jsou po třech lineárně nezávislé, proto $(1)$ platí
2. dvojice přímek $(a_1, b_1, c_1)$ a $(a_2, b_2, c_2)$ určují jeden bod:
   • jsou lineárně nezávislé a dimenze jádra následující matice je tedy $1$ a určují jeden bod (až na $\alpha$-násobek, což je definice bodů) $$\begin{pmatrix} a_1 & b_1 & c_1 \\ a_2 & b_2 & c_2 \end{pmatrix} \begin{pmatrix} x \\ y \\ t \end{pmatrix} = 0$$
3. analogické, protože role $(x, y, t)$ a $(a, b, c)$ je identická

5. přednáška

Latinské čtverce

Definice (latinský čtverec): řádu $n$ je tabulka $n \times n$ vyplněná čísly $[n]$, kde v žádném řádku či sloupci se symboly neopakují.

• (👀): $A$ je LČ $\implies$ po následujících operacích je stále:
  • permutace symbolů
  • permutace sloupců/řádků

Definice (ortogonalita): LČ $A, B$ jsou ortogonální, pokud pro každou dvojici symbolů $a, b \in [n]$ existují indexy $i, j \in [n]$ t. ž. $(A)_{i, j} = a, (B)_{i, j} = b$.

• když přeložím čtverce přes sebe, najdu políčko $(i, j)$ obsahující dvojici $(a, b)$
• (👀): počet dvojic symbolů $n^2 =$ počtu políček
  • zobrazení je bijekce
  • $\forall (a, b)$ se objeví v OLČ právě jednou
• (👀): $A, B$ jsou NOLČ $\implies$ pokud dělám operace z předchozího pozorování v obou čtvercích, tak ortogonalitu zachovávám, jinak nutně ne

Příklad: dvou navzájem ortogonálních latinských čtverců stupně $n$:

$$\begin{matrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{matrix} \qquad \begin{matrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ 2 & 1 & 4 & 3 \end{matrix}$$

Lemma: pro daný řád $n$ může existovat nejvýše $n - 1$ NOLČ.

Důkaz: mějme maximální rodinu NOLČ $L_1, \ldots, L_m$ a permutujme symboly tak, aby každý první řádek byl $1, 2, 3, \ldots, n$; uvažme symbol na pozici $(2, 1)$:

• není $1$, ta je na pozici $(1, 1)$
• není nějaké $k \in \left\{2, \ldots, n\right\}$ ve dvou čtvercích zároveň

Čtverců je dohromady tedy nejvýše $n - 1$.

Tvrzení: pokud $L_1, \ldots, L_{n - 1}$ jsou NOLČ, potom $\forall k, k', k \neq k', \forall l, l', l \neq l' \exists i: \left(L_i\right)_{k, l} = \left(L_i\right)_{k', l'}$

Důkaz: zpermutujeme symboly tak, aby $\forall i \left(L_i\right)_{k, l} = 1$:

$$\underbrace{\begin{bmatrix} & & & \\ & (1) & & \\ & & & \\ & & ? & \end{bmatrix} \qquad \begin{bmatrix} & & & \\ & (1) & & \\ & & & \\ & & ? & \end{bmatrix} \qquad \ldots \qquad \begin{bmatrix} & & & \\ & (1) & & \\ & & & \\ & & ? & \end{bmatrix}}_{n - 1}$$

Ve sloupci s otazníkem nemůže symbol $1$ být:

• v řádku s $(1)$
• ve dvou čtvercích na stejném místě

Mám tedy $n - 1$ možností a musím přijít na $n - 1$ různých řešení. Jedno z nich tedy vyjde na $?$.

NOLČ $\iff$ KPR

Věta: $\exists L_1, \ldots, L_{n - 1}$ NOLČ $\iff \exists KPR$ řádu $n$.

Důkaz (konstrukce $\Rightarrow$):

• dány čtverce $L_1, \ldots, L_{n - 1}$
• body: $r, s, l_1, l_{n - 1}, m_{1, 1}, m_{1, 2}, \ldots, m_{1, n}, \ldots, m_{n, n}$
• přímky:
  • $\mathrm{I}: \left\{r, s, l_1, \ldots, l_n - 1\right\}$
  • $\mathrm{II}:$ řádky – $\forall i \in [n]: \left\{r, m_{i, 1}, m_{i, 2}, \ldots, m_{i, n}\right\}$
  • $\mathrm{III}:$ sloupce – $\forall i \in [n]: \left\{s, m_{1, i}, m_{2, i}, \ldots, m_{n, i}\right\}$
  • $\mathrm{IV}: \underbrace{\forall i \in [n]}_{\text{latinské čtverce}}, \underbrace{\forall j \in [n]}_{\text{symboly}}: \left\{l_i\right\} \cup \left\{m_{k, l}\ \mid\ \left(L_i\right)_{k, l} = j\right\}$

Ověření axiomů:

1. $\mathcal{C} = \left\{r, s, m_{1, 1}, m_{2, 2}\right\}$
2. mezi:
   • $I, II \rightarrow r$
   • $I, III \rightarrow s$
   • $I, IV \rightarrow l_i$
   • $II, II \rightarrow r$
   • $III, III \rightarrow s$
   • $II, III \rightarrow m_{k, l}$
   • $II, IV \rightarrow$ čtverec je latinský, na řádku se symbol někde vyskytuje
   • $III, IV \rightarrow$ obdobně ^
   • $IV, IV \rightarrow$
     • různé čtverce: přesně definice ortogonality (existuje dvojice souřadnic pro dvojici symbolů)
     • stejné čtverce: $l_i$
3. mezi:
   • $r, s, l_i \rightarrow \mathrm{I}$
   • $r, m_{k, l} \rightarrow \mathrm{II}$
   • $s, m_{k, l} \rightarrow \mathrm{III}$
   • $l_{i}, m_{k, l} \rightarrow \mathrm{IV}$, symbol $\left(L_i\right)_{k, l}$ určuje, o kterou přímku z $l_i$ jde
   • $m_{k, l}, m_{k', l'} \rightarrow$
     • stejný řádek: $\mathrm{II}$
     • stejný sloupec: $\mathrm{III}$
     • jinak: $\mathrm{IV}$ a existuje, vycházíme z minulého pozorování

Důkaz (konstrukce $\Leftarrow$):

• dána KPR $(X, \mathcal{P})$, hledáme $L_1, \ldots, L_{n - 1}$
  1. zvolíme libovolně přímku $I = \left\{r, s, l_1, \ldots, l_{n - 1}\right\}$
  2. $\exists n$ přímek protínající $r$ – typ $\mathrm{II}$ a opět oindexuji body
  3. analogicky ^, typ $\mathrm{III}$, průsečíky jsou $m_{k, l}$
  4. pro bod $l_i$ oindexuj přímky $Q_1, \ldots, Q_n$; čtverec $L_i$ má $1$ na indexech $Q_1$, $2$ na $Q_2$, $\ldots$

Jsou NOLČ, protože:

• průsečíky $\mathrm{IV}$ s $\mathrm{II}, \mathrm{III}$ jsou jednoznačné $\implies$ čtverce jsou latinské
• jednoznačnost průniku dvou přímek typu $\mathrm{IV}$ – dvě různé přímky typu $\mathrm{IV}$ odpovídající dvěma různým čtvercům dávají souřadnici, kde se má dvojice symbolů nachází $\implies$ ortogonalita

6. přednáška

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

Tvrzení: počet podmnožin $X = \left| \binom{X}{k}\right| = \binom{|X|}{k}$

Důkaz: nechť máme bublinu s tečkami, každá reprezentuje uspořádanou $k$-tici prvků z $X$.

• počet teček $= n (n -1) (n-2) \ldots (n - k + 1) = \frac{n!}{(n - k)!}$ (vyberu $1.$ prvek, $2.$ prvek,…)
• v každé buňce $k$-tic (ekvivalenční třídě přes příslušnou relaci) se stejnými prvky je $k!$ prvků, počet buňek je to, co chceme (neuspořádaná $k$-tice)

$$\begin{aligned} \frac{n!}{(n - k)!} &= \left|\binom{X}{k}\right| \cdot k! \\ \left|\binom{X}{k}\right|&= \frac{n!}{(n - k)! k!} = \binom{n}{k} \\ \end{aligned}$$

Věta (Spernerova): nechť $(\mathcal{P}, \subseteq)$ je částečné uspořádání, kde $\mathcal{P}$ je množinový systém. Nechť $\mathcal{M}$ je největší antiřetězec ($\forall M_1, M_2 \in \mathcal{M}, M_1 \neq M_2: M_1 \nsubseteq M_2 \land M_2 \nsubseteq M_1$). Pak $|\mathcal{M}| \le \binom{n}{\left\lceil \frac{n}{2} \right\rceil}$, kde $n = |X|$.

Tvrzení (pomocné): $\sum_{M \in \mathcal{M}} \left|M\right|! (n - \left|M\right|)! \le n!$. Přes dvojí počítání počtu permutací na $X$:

• počet permutací $= n!$ (očividné)
• počet permutací $\ge \sum_{M \in \mathcal{M}} |M|! (n - |M|)!$, protože:
  • pro každé $M$ dostanu jinou množinu permutaci
  • $M$ určuje množinu permutací takovou, že nejprve permutuji $M$, potom $X \setminus M$: