slama.dev

Kombinatorika a Grafy I

2. 1. 2021; lecture notes

Úvodní informace

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

1. přednáška

Odhady faktoriálu

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

Důkaz \ge: (n!)2=123nn(n1)21=i=1n(i(ni+1)) \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:

aba+b2i(n+1i)i+n+1i2=n+12 \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!=i=1ni(ni+1)(n+12)nn! = \prod_{i = 1}^{n} \sqrt{i \cdot (n - i + 1)}\le \left(\frac{n + 1}{2}\right)^n

Důkaz \le:

ni(ni+1),i[n]n \le i (n - i + 1), \forall i \in [n]:

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

(n!)2=i=1ni(ni+1)i=1nn=nnn!nn/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(ne)nn!en(ne)n e\left(\frac{n}{e}\right)^n \le n! \le en \left(\frac{n}{e}\right)^n

Důkaz (indukcí):

  • n=1n = 1: 1e11e1 \le e \cdot 1 \cdot \frac{1}{e}
  • n1nn - 1 \rightarrow n: n!=n(n1)!IPen(n1)(n1e)n1=en(ne)n(en)n(n1)(n1e)n1=en(ne)n(n1n)ne1\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 1\le 1:

(11n)ne(e1n)ne=e1e=11+xex \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.: ab    a=bca \le b \implies a = b c pro c1c \le 1, proto to vlastně děláme
  • pro dolní mez postupujeme podobně, ale je potřeba indukční krok dokazovat pro nn+1n \rightarrow n+1, místo n1nn-1 \rightarrow n.

Věta (Stirlingova formule) (bez důkazu): n!2πn(ne)nn! \cong \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n

Odhady binomických koeficientů

(👀) pro malé k<<n(nk)=n!(nk)!k!=n(n1)(nk+1)k!nkk << 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): 2nn+1(nn/2)2n\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 2n2^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): 22m2m(2mm)22m2m\frac{2^{2m}}{2 \sqrt{m}} \le \binom{2m}{m} \le \frac{2^{2m}}{\sqrt{2m}}

Důkaz:

Nejprve jedno kouzlo: P=135(2m1)2462m=135(2m1)2462m2462m2462m=(2m)!22m(m!)2=(2mm)22m 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}}

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

Pak ještě druhé kouzlo: (1122)(1142)(11(2m)2)=(1322)(3544)((2m1)(2m+1)(2m)2)=P2(2m+1)<1// soucˇin veˇcıˊ <1 \begin{aligned} \left(1 - \frac{1}{2^2}\right) \left(1 - \frac{1}{4^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: P2<12m+1<12mP<12m \begin{aligned} P^2 &< \frac{1}{2m + 1} < \frac{1}{2m} \\ P &< \frac{1}{\sqrt{2m}} \\ \end{aligned}

Druhá strana analogicky (uvažujeme (1132)(1152)=(2432)(4652)=12(2m)P2\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ázky (v Z1\mathbb{Z}^1): Náhodný proces, v každém kroku se panáček začínající v bodu 00 posune ze své aktuální pozice doprava nebo doleva.

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

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

  • IS2nI_{S_{2n}}\ldots indikátor, že nastal jev „po 2n2n krocích jsem v počátku“
  • E[X]=E[#naˊvratu˚ do pocˇaˊtku]\mathbb{E}[X] = \mathbb{E}[\#\text{návratů do počátku}].
  • Pr[po 2n krocıˊch jsem v pocˇaˊtku]=(2nn)/22n\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 2n2n kroků

(2nn)22n22n2n22n=12n \frac{\binom{2n}{n}}{2^{2n}} \ge \frac{\frac{2^{2n}}{2 \sqrt{n}}}{2^{2n}} = \frac{1}{2 \sqrt{n}}

E[X]=E[i=1IS2i]=i=1E[IS2i]// linearita strˇednıˊ hodnoty=i=1Pr[IS2i]// strˇednıˊ hodnota indikaˊtoru je pravdeˇpodobnosti=112i// pouzˇitıˊ odhadu vyˊsˇe; diverguje \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 2D2D to také platí, ale ve 3D3D už ne (konverguje k nějakému konstantnímu číslu)!

Generující funkce

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

Příklad: a0=a1==11+x+x2+a_0 = a_1 = \ldots = 1 \mapsto 1 +x + x^2 + \ldots

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

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

Definice (vytvořující/generující funkce): nechť (a0,a1,)\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)=i=0aixia(x) = \sum_{i = 0}^{\infty} a_i x^i.

Operace na funkcích
operace řada úprava
součet a0+b0,a1+b1,a2+b2,a_0 + b_0, a_1 + b_1, a_2 + b_2, \ldots a(x)+b(x)a(x) + b(x)
násobek αa0,αa1,αa2,\alpha a_0, \alpha a_1, \alpha a_2, \ldots αa(x)\alpha a(x)
     
posun doprava 0,a0,a1,0, a_0, a_1, \ldots xa(x)xa(x)
posun doleva a1,a2,a3,a_1, a_2, a_3, \ldots a(x)a0x\frac{a(x) - a_0}{x}
     
substituce αx\alpha x a0,αa1,α2a2,a_0, \alpha a_1, \alpha^2 a_2, \ldots a(αx)a(\alpha x)
substituce xnx^n a0,0,n1,0,a1,0,n1,0,a2,a_0, 0, \overset{n - 1}{\ldots}, 0, a_1, 0, \overset{n - 1}{\ldots}, 0, a_2, \ldots a(xn)a(x^n)
     
derivace a1,2a2,3a3,a_1, 2a_2, 3a_3, \ldots a(x) a'(x)
integrování 0,a1,a2/2,a3/3,0, a_1, a_2/2, a_3/3, \ldots 0xa(t)dt \int_{0}^{x} a(t) dt
     
konvoluce k=0nakbnk \sum_{k = 0}^{n} a_k \cdot b_{n - k} a(x)b(x) a(x) \cdot b(x)

Všechny důkazy jsou jednoduché rozepsání z definice.

Zobecněná binomická věta

Tvrzení: rR,kNr \in \mathbb{R}, k \in \mathbb{N}, def. (rk)=r(r1)(r2)(rk+1)k!\binom{r}{k} = \frac{r \cdot (r - 1) \cdot (r - 2) \cdot \ldots \cdot (r - k + 1)}{k!}

  • pro rNr \in \mathbb{N} se shoduje s tím, co už známe
  • vyplývá z toho, že funkce (1+x)r(1 + x)^r je vytvořující funkcí posloupnosti ((r0),(r1),(r2),)\left(\binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots\right)
  • (👀) pokud rr je záporné celé, pak (rk)=(1)k(r+k1k)=(1)k(r+k1r1)\binom{r}{k} = (-1)^k \binom{-r + k - 1}{k} = (-1)^k \binom{-r + k - 1}{-r - 1}, tedy 1(1x)n=(1x)n=(n1n1)+(nn1)x+(n+1n1)x2+\frac{1}{(1 - x)^n} = (1 - x)^{-n} = \binom{n - 1}{n - 1} + \binom{n}{n - 1}x + \binom{n + 1}{n - 1}x^2 + \ldots

Příklad: V krabici je 3030 červených, 4040 žlutých a 5050 zelených míčků. Kolika způsoby lze vybrat 7070?

(1+x++x30)(1+x++x40)(1+x++x50)==1x311x1x411x1x511x// posuneme o 31 mıˊst a odecˇteme=1(1x)3(1x31)(1x41)(1x51)=((22)+(32)x+(42)x2+)(1x31)(1x41)(1x51)=1++[(722)(72312)(72412)(72512)]x70+=1061 \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 11 a z první závorky koeficient u 7070
  • ze druhé x31x^{31} a z první koeficient u 723172 - 31
    • analogicky pro 4141 a 5151 ze třetí a čtvrté

3. přednáška

Fibonacciho čísla

Definice: F0=0,F1=1,Fn=Fn1+Fn2,n2F_0 = 0, F_1 = 1, F_n = F_{n - 1} + F_{n - 2}, \forall n \ge 2

  • F(x)=F0+F1x+F2x2+F3x3F(x) = F_0 + F_1x + F_2x^2 + F_3x^3
F0F_0 F1F_1 F2F_2 F3F_3 F4F_4 Vytvořující funkce
00 11 F0+F1F_0 + F_1 F1+F2F_1 + F_2 F2+F3F_2 + F_3 F(x)F(x)
00 00 F1F_1 F2F_2 F3F_3 xF(x)x F(x)
00 00 F0F_0 F1F_1 F2F_2 x2F(x)x^2 F(x)
00 11 00 00 00 xx

Algebraickou úpravou dostáváme: F(x)=x1xx2=x(11+52x)(1152x)// algebra=1511+52x151152x// parciaˊlnıˊ zlomky =15(111+52x11152x)// tvary ±11λ1,2x \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 - \lambda_{1, 2} x}$}\\ \end{aligned}

Pro daný koeficient vytvořující funkce tedy máme: Fn=15[(1+52)n(152)njde k 0]=15(1+52)n \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

  • bn=b_n = počet binárních zakořeněných stromů na nn vrcholech
    • bn=k=0n1bkbnk+1b_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)=xb(x)b(x)+1b(x) = x \cdot b(x) \cdot b(x) + 1
      • xx je tam kvůli posunu, aby vycházelo správně indexování (suma nejde do nn)
      • 11 je tam kvůli tomu, aby nultý člen správně vycházel

Rekurence pro bnb_n vypadá skoro jako konvoluce sama sebe, takže by se nám líbilo něco jako b(x)=b(x)2b(x) = b(x)^2. Jenže narozdíl od konvoluce pronásobujeme jen prvních n1n-1 prvků. Uvažme tedy posloupnost 0,b0,b1,b2,0, b_0, b_1, b_2, \ldots generovanou funkcí xb(x)x b(x). Ta je již skoro konvolucí sama sebe – nn-tý prvek se v sumě požere s nulou. Jediná nepřesnost je u b0b_0, protože podle definice konvoluce b0=0b0+b00=0b_0 = 0 \cdot b_0 + b_0 \cdot 0 = 0, ale my víme b0=1b_0 = 1. Stačí tedy přičíst jedničku posunutou o jedna doprava, čímž dostaneme xb(x)=(xb(x))2+xx b(x) = (x b(x))^2 + x. Jinými slovy b(x)=xb(x)2+1b(x) = x b(x)^2 + 1.

b(x)=xb(x)2+1b(x)1,2=1±14x2x// ten s + nedaˊvaˊ smysl, divergujeb(x)=11k=1(4)k(1/2k)xk2x// 14k=ZBVk=0(4)k(1/2k)xk=12k=1(4)k(1/2k)xk1bn=12(4)n+1(1/2n+1)// konkreˊtnıˊ koeficient=12(1)n22n+212(121)n+1(12n)(n+1)!=12(1)n22n+212(12)n+1(2n12)(n+1)!=1222n+212122n12(n+1)!// kraˊcenıˊ zaˊpornyˊch cˇıˊsel=2n135(2n1)(n+1)!n!n!// kraˊcenıˊ 2=135(2n1)(n+1)n!2462nn!// rozdistribuovaˊnıˊ 2=1n+1(2n)!(n!)2=1n+1(2nn) \begin{aligned} b(x) &= x \cdot b(x)^2 + 1 \\ b(x)_{1, 2} &= \frac{1 \pm \sqrt{1 - 4x}}{2x} \qquad //\ \text{ten s $+$ 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{ZBV}}{=} \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}

Konečné projektivní roviny

První axiom zajišťuje netrivialitu. Není těžké si rozmyslet, že lze nahradit axiomem “Existují alespoň 2 různé přímky, z nichž každá má alespoň 3 body”. Bez některé z těchto podmínek by definici vyhovovala např. libovolně velká množina bodů s právě jednou přímkou, která by všechny body spojovala. Případně by k tomuto schématu šel přidat ještě jeden bod, který by s každým dalším byl spojen dvoubodovou přímkou.

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

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

Příklad (Fanova rovina):

Fanova rovina.

Počet bodů a přímek

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

Pomocné tvrzení: P,PPzX\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 CˇČ:

  • pokud nevedou přes všechny body z CˇČ, pak máme vyhráno
  • pokud vedou, tak existují dvě další přímky P1P_1 a P2P_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
  • P1PP_1 \neq P, protože pak by PP obsahovala alespoň 3 body z CˇČ. Podobně ostatní nerovnosti.

4. přednáška

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

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

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

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

Důkaz:

Explicitní důkaz (3): Pro každý bod započítejme všechny přímky jím procházející. Dostaneme tak (n2+n+1)(n+1)(n^2+n+1)(n+1) přímek. Ale každou jsme započítali (n+1)(n+1)-krát – jednou pro každý z jejích bodů.

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

Vezměme libovolné xXx \in X. Pak PP:x∉P\exists P \in \mathcal{P}: x \not\in P, protože vezmeme-li body a,b,cCˇa, b, c \in Č, pak přímky abab a acac nemohou mít další společný bod než aa (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 xx a ta by rovněž někde protínala PP (a nesplňovala tak axiomy).

Bodů na obrázku je 1x+(n+1)P0Pnnbody Pi, bez x=n2+n+1\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,S)(X, \mathcal{S}) je množinový systém (S2X\mathcal{S} \subseteq 2^X). Jeho incidenční graf je bipartitní graf (V=XS,E={(x,s)X×S  xs})\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,T)(Y, \mathcal{T}) je duál (X,S)(X, \mathcal{S}) pokud Y=SY = \mathcal{S} a T={{sS  xs}  xX}\mathcal{T} = \left\{\left\{s \in \mathcal{S}\ |\ x \in s\right\}\ |\ x \in X\right\}

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

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

Duál Fanovy roviny.

Tvrzení: duál KPR je KPR.

  1. „každá přímka obsahuje 2\le 2 body z CˇČ
  2. „každé dvě přímky se protínají právě v 11 bodě“
  3. „každé dva body určují právě 11 přímku“

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

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

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

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

Konstrukce KPR

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

  • T=K3(0,0,0)T = \mathbb{K}^3 \setminus \left(0, 0, 0\right)
  • na TT zavedu ekvivalenci (x,y,t)T(x, y, t) \in T je ekvivalentní s (λx,λy,λt),λK0(\lambda x, \lambda y, \lambda t), \forall \lambda \in \mathbb{K} \setminus {0}
  • body XX jsou ekvivalenční třídy nad TT
  • reprezentanti: poslední nenulová složka je 11
    • trojice tvaru (x,y,1),(x,1,0),(1,0,0)(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 n2+n+1n^2 + n + 1, což sedí
  • přímky P\mathcal{P}: pro každou (a,b,c)T(a, b, c) \in T definujeme přímku Pa,b,cP_{a, b, c} jako množinu bodů (x,y,t)(x, y, t) splňující ax+by+ct=0ax + by + ct = 0
    • (x,y,t)T,λ0:(x,y,t)\forall (x, y, t) \in T, \forall \lambda \neq 0: (x, y, t) splňuje     (λx,λy,λt)\iff (\lambda x, \lambda y, \lambda t) splňuje
    • (a,b,c)T,λ\forall (a, b, c) \in T, \forall \lambda fixuji (x,y,t)T:ax+by+ct=0    λax+λby+λct=0    (x, y, t) \in T: ax + by + ct = 0 \iff \lambda ax + \lambda by + \lambda ct = 0 \implies přímky Pa,b,c=Pλa,λb,λc    P=XP_{a, b, c} = P_{\lambda a, \lambda b, \lambda c} \implies |\mathcal{P}| = |X| a mohu si opět zvolit reprezentanty

  1. „každá přímka obsahuje 2\le 2 body z CˇČ
  2. „každé dvě přímky se protínají právě v 11 bodě“
  3. „každé dva body určují právě 11 přímku“

Ověření axiomů:

  1. Cˇ={(1,0,0),(0,1,0),(0,0,1),(1,1,1)}Č = \left\{(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)\right\}
    • jsou po třech lineárně nezávislé, proto (1)(1) platí
  2. dvojice přímek (a1,b1,c1)(a_1, b_1, c_1) a (a2,b2,c2)(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 11 a určují jeden bod (až na α\alpha-násobek, což je definice bodů) (a1b1c1a2b2c2)(xyt)=0 \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)(x, y, t) a (a,b,c)(a, b, c) je identická

5. přednáška

Latinské čtverce

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

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

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

  • když přeložím čtverce přes sebe, najdu políčko (i,j)(i, j) obsahující dvojici (a,b)(a, b)
  • (👀) počet dvojic symbolů n2=n^2 = počtu políček
    • zobrazení je bijekce
    • (a,b)\forall (a, b) se objeví v OLČ právě jednou
  • (👀) A,BA, 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ě nn:

12342143341243211234341243212143 \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 nn může existovat nejvýše n1n - 1 NOLČ.

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

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

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

Pro libovolné dvě pozice (které se liší v řádku a sloupci) existuje čtverec, který na nich má stejné hodnoty.

Tvrzení: pokud L1,,Ln1L_1, \ldots, L_{n - 1} jsou NOLČ, potom k,k,kk,l,l,lli:(Li)k,l=(Li)k,l\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 i(Li)k,l=1\forall i \left(L_i\right)_{k, l} = 1:

[(1)?][(1)?][(1)?]n1 \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 11 být:

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

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

NOLČ     \iff KPR

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

Důkaz: konstrukce \Rightarrow

  • dány čtverce L1,,Ln1L_1, \ldots, L_{n - 1}
  • body: r,s,l1,ln1,m1,1,m1,2,,m1,n,,mn,nr, s, l_1, l_{n - 1}, m_{1, 1}, m_{1, 2}, \ldots, m_{1, n}, \ldots, m_{n, n}
  • přímky:
    • I:{r,s,l1,,ln1}\mathrm{I}: \left\{r, s, l_1, \ldots, l_n - 1\right\}
    • II:\mathrm{II}: řádky – i[n]:{r,mi,1,mi,2,,mi,n}\forall i \in [n]: \left\{r, m_{i, 1}, m_{i, 2}, \ldots, m_{i, n}\right\}
    • III:\mathrm{III}: sloupce – i[n]:{s,m1,i,m2,i,,mn,i}\forall i \in [n]: \left\{s, m_{1, i}, m_{2, i}, \ldots, m_{n, i}\right\}
    • IV:i[n]latinskeˊ cˇtverce,j[n]symboly:{li}{mk,l  (Li)k,l=j}\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\}

Latinský čtverec na KPR.

  1. „každá přímka obsahuje 2\le 2 body z CˇČ
  2. „každé dvě přímky se protínají právě v 11 bodě“
  3. „každé dva body určují právě 11 přímku“

Ověření axiomů:

  1. Cˇ={r,s,m1,1,m2,2}Č = \left\{r, s, m_{1, 1}, m_{2, 2}\right\}
  2. mezi:
    • I,IIrI, II \rightarrow r
    • I,IIIsI, III \rightarrow s
    • I,IVliI, IV \rightarrow l_i
    • II,IIrII, II \rightarrow r
    • III,IIIsIII, III \rightarrow s
    • II,IIImk,lII, III \rightarrow m_{k, l}
    • II,IVII, IV \rightarrow čtverec je latinský, na řádku se symbol někde vyskytuje
    • III,IVIII, IV \rightarrow obdobně ^
    • IV,IVIV, IV \rightarrow
      • různé čtverce: přesně definice ortogonality (existuje dvojice souřadnic pro dvojici symbolů)
      • stejné čtverce: lil_i
  3. mezi:
    • r,s,liIr, s, l_i \rightarrow \mathrm{I}
    • r,mk,lIIr, m_{k, l} \rightarrow \mathrm{II}
    • s,mk,lIIIs, m_{k, l} \rightarrow \mathrm{III}
    • li,mk,lIVl_{i}, m_{k, l} \rightarrow \mathrm{IV}, symbol (Li)k,l\left(L_i\right)_{k, l} určuje, o kterou přímku z lil_i jde
    • mk,l,mk,lm_{k, l}, m_{k', l'} \rightarrow
      • stejný řádek: II\mathrm{II}
      • stejný sloupec: III\mathrm{III}
      • jinak: IV\mathrm{IV} a existuje, vycházíme z minulého pozorování

Důkaz: konstrukce \Leftarrow

  • dána KPR (X,P)(X, \mathcal{P}), hledáme L1,,Ln1L_1, \ldots, L_{n - 1}
    1. zvolíme libovolně přímku I={r,s,l1,,ln1}I = \left\{r, s, l_1, \ldots, l_{n - 1}\right\}
    2. n\exists n přímek protínající rr – typ II\mathrm{II} a opět oindexuji body
    3. analogicky ^, typ III\mathrm{III}, průsečíky jsou mk,lm_{k, l}
    4. pro bod lil_i oindexuj přímky Q1,,QnQ_1, \ldots, Q_n; čtverec LiL_i11 na indexech Q1Q_1, 22 na Q2Q_2, \ldots

Jsou NOLČ, protože:

  • průsečíky IV\mathrm{IV} s II,III\mathrm{II}, \mathrm{III} jsou jednoznačné     \implies čtverce jsou latinské
  • jednoznačnost průniku dvou přímek typu IV\mathrm{IV} – dvě různé přímky typu IV\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

KPR na latinský čtverec.

6. přednáška

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

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

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

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

n!(nk)!=(Xk)k!(Xk)=n!(nk)!k!=(nk) \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ť (P,)(\mathcal{P}, \subseteq) je částečné uspořádání, kde P\mathcal{P} je množinový systém. Nechť M\mathcal{M} je největší antiřetězec (M1,M2M,M1M2:M1M2M2M1\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 M(nn2)|\mathcal{M}| \le \binom{n}{\left\lceil \frac{n}{2} \right\rceil}, kde n=Xn = |X|.

Sperenerova věta.

Pomocné tvrzení: MMM!(nM)!n!