Kombagra 1
Higher beings, these words are for you alone. Občas tu je něco blbě tak bacha
Spolupachatel skript Hanek Javatý.

Balls
Odhady
[P: chapter 1, MN: chapter 3]
Odhady faktoriálů
Nejdříve dokážeme AG nerovnost, kterou použijeme při důkazu tvrzení níže. Actually that was a lie ale nechám to tady jelikož už sem to vyoval.
AG nerovnost
Každý z těchto činitelů , . To protože na okrajích nebo je to zjevně .
V intervalu je a
tudíž
Nyní ta těžší nerovnost
Předem se omlouvám, je to convoluted AF. Obrázek je důležitej, vlastně zavíráme mezi dva integrály co má jiný meze.
Spodní odhad. Pojďme se podívat na to, jak se chová funkce .
modrá část.
tedy odpovídá modré části. Ta je určitě větší než červená, což je integrál od do .
Červená:
Můžeme z logaritmu udělat výsledek itegrálu tím hodnotu zmenšit.
K dokázání horního odhadu nám pomůže zelená část. Je vlastně stejná jako ta modrá, akorát je posunutá doprava. Pokud budeme porovnávat její hodnotu s červenou částí, tak červená bude větší, musíme ji ale také posunout. Integrál bude tedy od do
Nyní opět evil matematický dosazení aby nám vyšlo to co chceme. Za dosadíme .
Celkově tedy
🔲
Stirling formula
Patří do analýzy nebo tak něco
Odhady binomického koeficientu
Spodní odhad
(důkaz roznásobením). Díky tomu
Horní odhad
Nechť . Všimni si že protože
Budiž vymyšlený výraz:
Na levé straně vynecháme sčítance za
Vydělíme
Na levé straně je každý koeficient , takže když je vynecháme tak stranu pouze zmenšíme.
Všimni si cool feature je že už tam je ten který chceme! Expandujeme .
(všimni si obrácení zlomku kterým dělíme)
využijeme fakt: () pro umlácení pravé strany:
tedy dostaneme
Vlevo zahodíme Binomické koeficienty které nás nezajímají (zase pouze zmenší)
🔲
Nyní se podívejme co se děje s prostředním binomickým koeficientem, ten by měl být řekněme největší (něco něco pascalův trojúhelník);
Nejdříve si pořiďme P. Vynásobíme 1 To nám pomůže, protože v dokazované nerovnosti jsou v čitatelích právě , takže nyní nám stačí dokázat
Horní odhad
Uvažme posloupnost , ta má ve výsledku v čitateli (skoro) všechna lichá čísla dvakrát a všechna sudá čísla ve jmenovateli dvakrát. Tado posloupnost se tedy rovná až na přebytek. Co zbývá? vlevo a vpravo. Jelikož každý činitel , tak dostáváme že , tedy Zmenšíme jmenovatel, takže zvětšíme pravou stranu.
Spodní odhad je podobný, ale má obrácené čitatele a jmenovatele. Uvažme posloupnost , Tato posloupnost se chová skoro stejně jako , až na přebytek v čitateli. Co přebývá? vlevo a vpravo. Tudíž Každý člen je opět , takže 🔲
Příklad: random walk. Kolikrát v průměru se dostaneme po 2m krocích zpátky do počátku, jestliže se v každém kroku rozhodneme jít náhodně doleva/doprava?
Řešení: po krocích existuje procházek které končí v 0. Celkem je tedy pravděpodobnost že po krocích jsme v nule. Suma přes všechny délky:
což diverguje. Po nekonečně krocích tedy můžeme očekávat nekonečně návšťev počátku.
Divergence se může ověřit vytáhnutím ven a omezení harmonickou řadou.
Vytvořující funkce
Motivační příklad, kolika způsoby jde vytáhnout 7 míčků z pytle ve kterém jsou 3 červené, 4 zelené a 5 modrých? Moudrý čtenář ví že je to konvoluce a ptáme se na koeficient .
Nechť je posloupnost reálných čísel. Vytvořující funkce této posloupnosti je řada
Poznámka: Spíše než nekonečná řada je důležitá uzavřená reprezentace vytvořující funkce. Např. řada je generovaná funkcí . Pokud je v intervalu , tak řada konverguje a má stejný součet. (Důkaz taylorova řada).
Z toho dostáváme jakousi podmínku pro to, aby posloupnost měla vytvořující funkci. Stačí, aby pro nějaké reálné a . Pak totiž pro řada konverguje.
Zajímavé je co se stane, když do VF dosadíme 0. V tu chvíli dostaneme první prvek , protože všechny ostatní se vynulují. Také je zajímavé derivovat VF. Tím se všechny členy posloupnosti posunou o jedna doleva a vydělí se předchozím exponentem. Kombinací těchto dvou faktů dostáváme vzorec pro -tý člen posloupnosti. Uděláme -tou derivaci, vydělíme a dosadíme .
Operace | Řada | Úprava |
---|---|---|
Součet | ||
Násobek | ||
Posun doprava | ||
Posun doleva | ||
Substituce | ||
Substituce | ||
Derivace | ||
Integrování | ||
Konvoluce |
Ověř si to :)
Teď dlouhej talk o tom jak vyjádřit uzavřeně nějakou hodnotu rekurentně zadané rovnice. Tldr: Zapiš si posloupnost jako řadu, vypiš prvních pár prvků abys tam měl ten člen co máš rekurentně zadanej.
Všimni si pár triků, např vytknutí před sumu. Poté dosaď rekurenci, roztrhni sumu a snaž se nekonečnou sumu nahradit za tvou VF. Neboj se podvádět, musíš přičítat nulté a první členy, zvracej zpátky do sumy, prostě se snaž dostat tvar . To pak nahraď za a vyřeš pro .
Potom dostaneš uzavřený tvar pro tvojí VF. Dostaň ji do tvarů to samé několikrát, kde není nutně a je konstanta. Nejspíš budeš řešit parciální zlomky. Pak se podívej do tabulky, vyhaluz posloupnosti co sčítáš a máš vzoreček pro . Snadné, že? :)
Přikládám svůj úkol protože si to nebudu pamatovat :)/
Zobecněná binomická věta
Prostě normální koeficient :)
Z toho plyne, že pro
Příklad: jak spočítat motivační příklad ale lépe.
V krabici je 30 červených, 40 žlutých a 50 zelených míčků. Kolika způsoby lze vybrat 70?
Wait, cože? <- tohle bys měl být ty. Jak jsme přišli na to že je nějakej random zlomek? Vem vytvořující funkci samých 1 a vynásob jí .
Co dostaneš? Normální vytvořující funkci (), od které ale odečítáš posunutou VF od . To znamená že ti zbyde jen .🪄
To ale znamená že máme funkci v uzavřené formě, a díky zobecněné binomické větě víme, že
A ptáme se na koeficient u , který
za samé 1, když vybereme atd…
Strom je buď prázdný, nebo má levý a pravý podstrom, které jsou také binárními stromy (můžou být prázdné)
Budeme počítat kolik jich je, počet různých binárních zakořeněných stromů na n vrcholech.
Lze si rozmyslet že , protože se rekurzíme na obě části, do každé přiřadíme část vrcholů. Když z toho uděláme VF, tak vychází, že
aby vycházelo správně a je posun. Pak už je to pouze konvoluce. Vyjádříme 🪄 - normální kvadratická rovnice. Na odmocninu použij zobecněnou binomickou větu (mocníš na ).
Vyjádření konkrétního koeficientu pak dává Catalanovo číslo
TODO #partitions of n into odd parts = #partitions of n into distinct parts [MN 12.7 / here]
Finite projective planes (fpp FPR)
[P: chapter 3, MN: chapter 9]
budiž:
- množina
- (některé podmnožiny )
Množinový systém je dvojice
Jako kdyby ale very nice✨ and neat✨ and all✨ (máme rádi FPR)
je množina bodů. je množina čar. je množinový systém.
- Existují 4 různé body takové že libovlná přímka protne maximálně 2 z nich.
- Libovolné 2 přímky mají právě jeden společný bod
- Libovolné 2 body mají právě jednu společnou přímku
Nechť FPR.
Všechny přímky mají stejný počet bodů.
Vemme libovolné . Nejprve pomocné pozorování:
Existuje bod který není ani na ani na
Vezmeme 4-prvkovou množinu z prvního axiomu. Máme a .
Pokud není podmnožina pak máme hotovo. Znamená to že alespoň jeden bod z je mimo i .
Jinak musí protínat ve 2 bodech a a zároveň musí protínat ve druhých 2 bodech a (více by bylo ve sporu s axiomem) ().
Pak vezmeme přímky:
- protíná a
- protíná a
Nechť je průnik s . Pak není v ani v .
a se protínají v bodě . Pokud by byl v pak by se a protínají v bodech i což je spor. Tudíž nemůže ležet na a analogicky ani na . 🔲
Ozbrojeni tímto pozorováním, a mají stejnou velikost, definujíc funkci .
Ukážeme, že je bijekce.
Neformálně: je náš sniping spot a jsou body skrz které střílíme do .
Vemme náš shiny bod mimo a definujme obraz (terč) pro jako průnik s přímkou která prochází body a (bullet trail).
Z axiomů 2 a 3 je terč dobře definovaný. Dvě různá musí mít různé obrazy $varphi(x), jinak by tyto dva bullet traily (přímky) sdílely více než jeden bod. Tudíž je bijekce.
Řád FPR je pro libovolné (všechny jsou stejně dlouhé).
(To je lehce otravné ale není to chyba…)
Pro FPR řádu :
Právě přímek prochází každým bodem
Nechť libovolný . Jistě máme která neobsahuje .
Pro každý vezmeme přímku procházející a . To je jistě přímka a jistě prochází a jistě jich je . Nice.
Ale co kdyby existovala nějaká další zlá přímka ? Taková by musela protnout ale zároveň každé 2 přímky mají společný bod takže existuje takže je jedno z a žádná zlá přímka neexistuje.
Vezmeme a bod mimo . Pak vyrobíme přímky kde protíná a . Každá má dalších bodů mimo , takže dohromady přímek obsahuje různých bodů plus samotné . .
(Jednotlivá nemohou sdílet těchto “ dalších bodů” protože pak by tyto 2 přímky sdíleli 2 body ( a tento jeden další))
Důkaz vypadne automaticky z toho minulého po researchnutí duality.
Dualita
Dualita znamená “prohození role přímky a bodu”. Pro přesnou formulaci si pro FPR zavedeme graf incidence.
Bipartitní graf kde v první partii vrcholy reprezentují přímky a v druhé partii vrcholy reprezentují body.
Mezi vrcholi je hrana pokud daný bod patří do dané přímky.
Pro dané FPR jeho duál dostaneme vyrobením grafu incidence, prohozením významu partií a přeinterpretováním transformovaného bipartitního grafu incidence zpět na FPR.
Duál FPR je také FPR
Budiž FPR a jeho duál , kde je systém podmnožin . Každý z těchto podmnožin odpovídá nějakému bodu z .
Všimněte si, že pro různé dostaneme různé podmnožiny .
Musíme ověřit axiomy FPR pro tento duál.
- Přeloženo pro duál říká: Existují 4 přímky takové že žádné 3 z nich nemají společný bod. Vezmeme z původního axiomu pro neduál. Z něj vyrobíme 4 přímky: , , , . Pro tyhle to platí.
- Je to samé jako 3. pro neduál!
- Je to samé jako 2. pro neduál!
Duál FPR řádu je FPR řádu
plyne z pozorování o počtu bodů na přímce a přímek procházející bodem
Existují FPR řádu 2, 3, 4, 5. 6 ne. 7, 8, 9 existují, 10 ne.
Existují pokud existuje těleso řádu (tedy pro prvočíslo ).
Konstrukce FPR z konečného tělesa.
- Prohlásíme že existují trojice prvků z tělesa.
- Budiž ekvivalence kde trojice kdyžž existuje nenulová z tělesa taková že , , .
- Body v FPR jsou třídy této ekvivalence KROM . (Takhle vyrobené FPR se často značí kde je to původní těleso)
- Přímky v tomto FPR jsou opět trojice prvků z tělesa bez .
- Bod leží na přímce kdyžž .
- Profit
Stačí dokázat axiomy:
Začneme s tím že 2 přímky sdílí právě 1 bod.
Nechť máme a , 3D vektory v tělese . Oba nenulové.
Jelikož oba nejsou násobky toho druhého, jsou lineárně nezávislé. Takže matice
má rank 2. Jukněme na sloupce jako 2D vektory. Víme že 3 vektory v 2D prostoru musí být lineárně závislé. Takže existují 3 čísla taková že ne všechny najednou jsou 0 kde:
Pokud toto přepíšeme pro každou souřadnici zvlášť, dostaneme že bod leží na obou přímkách!! (z definice ležení na přímce)
Zároveň ale protože rank matice je 2, musí existovat 2 lineárně nezávislé sloupce. Búno to jsou a . To znamená že pro libovolný vektor má unikátní řešení.
Takže pokud se koukneme na tamtu rovnici znova:
pak první 2 čelny jsou zašpendlíkované na místě a jediná vůle je v posledním členu když ho škálujeme čkem. ALE to znamená že rovnice může vycházet jen pro jednu hodnotu !
2 body sdílí právě 1 přímku
stejně jako 2 přimky sdílí 1 bod
existují 4 body takové že každá přímka protne max 2
Třeba: i think
Latinský čtverec
čtvercová tabulka řádků a sloupců. V každém políčku je jedno číslo od do .
Každé číslo se objevuje právě jednou v každém sloupečku a právě jednou v každém řádku.
Když vezmu 2 a transparentně je položím na sebe, v každém z políček dostanu dvojici čísel. Tyto 2 LČ jsou ortogonální pokud se žádná dvojice nezopakuje.
(Jelikož dvojic je , každá dvojice se ve skutečnosti musí objevit právě jednou)
Počet ortogonálních latinských čtverců řádu je maximálně
Nejprve pozorování: Budiž ortogonální latinské čtverce a oba řádu a permutace čísel .
Vyrobíme nový latinský čtverec . Ten bude mít na pozici číslo (kde je pozice v LČ ).
Po rozmyšlení je vidět že i je ortogonální k . Tudíž:
Ortogonalita LČ se nezmění přejmenováním symbolů v jednom z nich.
Představme si latinské čtverce každé 2 z nich ortogonální.
Pro každé : permutujme jeho symboly tak aby měl na prvním řádku bylo .
Podle pozorování víme, že i tyto jsou každý s každým ortogonální.
Jukněme, co může být na pozici některého :
- určitě ne . Ta už je ve stejném sloupci na .
- žádné 2 tam nemůžou mít stejné číslo. Kdyby tam měli stejné číslo, jejich dvojice by na měla dvojici ale ta se už objevila na tém místě prvního řádku! tudíž mohou být na pozici pouze v jednom takže . 🔲
Pro existuje FPR řádu pokudd existuje navzájem ortogonálních LČ řádu .
Nejprve sestrojíme FPR řádu z navzájem ortogonálních LČ řádu .
Jako template vezmem fancy tvar:
a teď si všimni že tam je dost bodů ale málo čar. Takže podle těch LČ které jsme stále nepoužili budeme proplétat nové přímky tím gridem vpravo dole.
Pro každé a vyrobíme přímku:
Tzn: Začneme přímku v a tam kde má LČ políčko s číslem appendneme do přímky.
Tohle je určitě FPR (důkaz vymysli na místě). Jde provést pozpátku pro vytvoření LČ z FPR. Stačí vybrat a libovolně.🔲
Numberphile video about M.O.L.S.
Toky v sítích
Takovej speedrun protože to určitě umíme.
Síť je čtveřice . je graf (dvojice množiny vrcholů a relace), a jsou vrcholy (source a sink) a c je funkce z hran do .
Tok je pak funkce která dává hranám ohodnocení.
Pravidla pro toky:
- - nemůžu hraně dát víc než co se do ní vejde
- , neboli do vrcholu teče stejně jako odtéká [P: chapter 4.1, 4.2, 4.3]
je velikost toku, třeba přebytek ve stoku
Každá síť má maximální tok - sketch, asi přes rozbor algoritmu xd
Řez je množina hran po jejichž odstranění se graf rozpadne na více komponent
Je to vlastně to samý, ale komponenty musí být 2. Obv zdroj je v A a stok je v B.
- elementární řez je taky řez a
- Každý řez obsahuje elementární řez.
Takový hrátky z cestami. v (i) si pořidíme cestu z do a říkáme, že jedna z hran této cesty je v řezu. To je vidět, protože a jsou v jiných komponentách.
ve (ii) je to to samé. Máme řez . Pořídíme a , A bude množina vrcholů do kterých se dá dostat v z a bude její doplněk. Pak tvrdíme že . Kdyby nebyl, tak existuje hrana v , a . Pak ale cesta do y nekřižuje R, tedy je ve stejné komponentě jako a tedy musí být v .
Ano, je to kokotina.
Zadefinujeme přebytek na vrcholu -tj. rozdíl mezi přítokem a odtokem. Tento rozdíl je pak roven . První rovnost rozborem případů kudy vede hrana, druhá rovnost je triviální - všechny vrcholy mají přebytek 0.
Zlepšující hrany (augmenting path), věta o tom že maximální tok je roven minimálnímu řezu. [P 4.2.5], známe z primy.
Ford-Fulkerson algoritmus hledá cesty v síti rezerv. Když ji najde, tak ji přičte do toku. Na celočíselných hranách se zastaví a vydá maximální tok. (bez důkazu)
[P: chapter 4.4, 4.5]
Nechť je konečný systém konečných množin. Nechť je sjednocení všech množin . Potom funkci nazveme systém různých reprezen- tantů právě tehdy, když je prostá a současně .
Buď graf a buď množina dvojic vrcholů . Pak nazveme párování v grafu právě tehdy, když je každý vrchol v nejvýše jedné dvojici v .
Nechť je konečný systém konečných množin. Pak platí, že má systém různých reprezentantů právě tehdy, když pro každou a sjednocení všech jejích prvků platí .
Nechť G = (V, E) je bipartitní graf s parti tami X a Y . Pak má G párování obsahující všechny vrcholy partity X právě tehdy, když pro každou M ⊆ X platí, že z ní vedou hrany k alespoň |M | různým vrcholům Y.
DŮ
König-Egerváry theorem
Velikost maximálního párování v bipartitním grafu je rovna minimální velikosti vrcholového pokrytí (proof ommited, ale docela obvious). N
- Defect Hall theorem
- Existence of a perfect matching in a regular bipartite graph
Grafová souvislost
[P: chapter 5.1, 5.2]
Pokud je pak to je JINAK
je velikost nejmenšího vrcholového řezu .
je velikost nejmenšího hranového řezu.
je hranově/vrcholově -souvislý pokud .
Pro graf s alespoň 2 vrcholy:
“Odebráním libovolné hrany se může jedině snížit a to maximálně o 1”
“Odebráním libovolné množiny hran se může jedině snížit”
To první jistě plyne z toho druhého
se po odebrání hrany sníží maximálně o 1 ()
- Vezmeme velkou
- Pak .
- Takže .
Z toho plyne že je spojitý. ale $abs(F’)
Ford-Fulkerson theorem: A graph is k-edge-connected iff for every 2 vertices there exist k edge-disjoint paths
Menger theorem: A graph is k-vertex-connected iff for every 2 vertices there exist k vertex-disjoint paths (stated).
bonus: Another notion to measure how well connected a graph is: expansion
Graph connectivity cont’d and double counting
[P: chapter 5.3] and [P: chapter 6.3, 6.4]
- bridge, articulation, edge subdivision
- subdividing an edge of a vertex-2-connected graph preserves vertex-2-connectivity
- Ear lemma
Graf je vrcholově 2-souvislý právě tehdy když zle sestrojit z cyklu kterému přilepujeme uši. (Ear lemma, ušní lema, ušizmus)
:
Cyklus je jistě vrcholově 2-souvislý. Přidáním ucha nemůže vzniknout vrchol takový že po jeho odebrání se graf rozpadne.
:
Budiž graf který je vrcholově 2-souvislý. K němu vyrobíme co největší podgraf který jsme vytvořili z cyklu a přilepování uší.
Tvrdím, že je indukovaný podgraf. Pokud ne, pak existuje dvojice vrcholů mezi kterýma nevede hrana v ale vede hrana v . Pak ale není největší možný. Tudíž musí být indukovaný.
Předpokládám že existuje vrchol, který je v ale není v . Jelikož je souvislý. Musí existovat dvojice vrcholů , která sousedí a je v ale ne.
Jelikož je vrcholově 2-souvislý, po odebrání se nemůže rozpadnout. Tudíž stále existuje cesta z do . To je ale ucho které jsme měli přidat takže všechny vrcholy jsou v .
Jelikož a mají stejné vrchly a jelikož je indukovaný podgraf, musí to být stejné grafy. 🔲
- Cayley’s formula for the number of spanning trees of a complete graph (proof due to Pitman by double-counting, see e.g. Wiki)
- Exercise: #spanning trees of a K_n minus one edge (stated).
- Sperner theorem about the size of the largest antichain in P([n])
- Graphs without a C_4 subgraph have O(n^{3/2}) edges (stated)
- bonus riddle (Erdős-Ko-Rado theorem): How many subsets of size 5 can you choose from {1,2,..,10} so that every 2 of them intersect?
Ramseyho teorie
Když máme dost velkou hromadu věcí tak v ní musí být nějaká struktura - Pepík
(syntax shugar: )
Pigeonhole principle
Množina kde každý prvek je obarvený jednou z barev.
Pak existuje barva která se objeví -krát
Pokud ne, pak je obarveno jen koulí.
6-členná party
Pokdu obarvíme hrany červeně a modře, pak existuje jednobarevný trojúhelník.
(Note: nefunguje pro . (pentagon s hvězdou uprostřed))
Vem vrchol. Koukni na 5 odchozích vrcholů. 3 z nich musí mít stejnou barvu BÚNO červená.
Teď jukni na tyhle 3 vrcholy. Můžou se stát 2 věci:
- Nějaké 2 mají taky červenou hranu mezi sebou takže výhra
- žádné 2 nemají červenou hranu mezi sebou takže! všechny 3 mají mezi sebou modrou hranu, což tvoří modrý trojúhelník.
je nejmenší možné číslo takové, že kdykoliv obarvujeme hrany grafu červeně a modře, pak existuje buď:
- podgraf kde jsou všechny hrany červené NEBO
- podgraf kde jsou všechny hrany modré.
(Poznámka: graf ve kterém hledáme musí být úplný. Grafy které hledáme musí být úplné)
Note: (6-členná party)
(Ramsey pro hrany a 2 barvy)
Indukcí po .
Init: pro nebo pak funguje haha. (bo má 0 hran takže pro ně platí všechno)
Indukční předpoklad:
Budiž a vem
Teď to přepíšeme aby to vypadalo holubníkovitě:
Vem , vrchol , a zase jukni na jeho hrany. Holub tvrdí že bude:
- červených hran NEBO
- modrých hran.
Pokud 1. pak z předpokladu víme že:
- buď červený sousedi obsahují červenou , pak po přidání dostaneme červenou
- nebo červený sousedi obsahují modrou , pak yay.
Jinak 2. pak analogicky pro modré sousedy.
lower bound
Chňapni kde a obarvi všechny hrany nezávisle.
Tohle nemusí fungovat obv ALE
Jak často se stane, že když vyberu množinu o vrcholech pak mají všechny stejnou barvu? well this:
Jaká je šance že nějaký -prvková množina vrcholů má všechny hrany stejné? well než počet -prvkových množin
něco něco idk nemám rád pravděpodobnost
IF YOU HAVE A SUFFICIENT AMOUNT OF BALLS
Budiž množina a .
je množina všech -prvkových podmnožin .
Nekonečná verze Ramseyovy věty pro hypergrafy (bro jestli tohle nezní cool tak idk)
Pro libovolné obarvení pomocí barev (barva je vlastnost podmnožiny)
existuje nekonečná množina kde dostanou stejnou barvu.
Indukce podél . Pro , barvíme pomocí barev, takže nějaká barva se objeví nekonečně mnoho krát.
Řekněme že pro , vem .
Nechť je barvení všech -tic pomocí barev .
postavíme podmnožiny kde a kde .
Pak předpokládáĺe že už máme a . Definujeme přiřazením barvy té -tici .
Indukcí, najdi nekonečnou podmnožinu $A_i+2 sube A_i$ tak že všechny
$p$-prvkové podmnožiny dostanou stejnou barvu.
König lemma (O nekonečných stromech)
(důkaz nebude ve zkoušce)
Pokud je nekonečný strom se všemi stupni konečnými.
Čapni libovolný vrchol. Pak existuje nekonečná cesta po z tohoto bodu.
(jakože lol obviously wtf)
(sketch) Vem vrchol jako kořen. ten má konečně mnoho sousedů. Jukněme na ně. Součet jejich velikostí je nekonečno. takže alespoň jeden ze sousedů musí být nekonečný strom. takže půjdeme tam. Ez done
Vibe: A teď tohle umí spoutat konečné a nekonečné struktury
Ramsey pro hypergrafy, konečný (still cool)
Vem . Pak existuje konečné číslo takové že kdykoliv obarvujeme kde pak
#(Dec 17): Ramsey theory, cont’d [P: chapter 7.3].:
Pro jakoukoliv množinu pěti bodů v rovině v obecné poloze (ne 3 na přímce) tvoří alespoň jedna čtveřice konvexní čtyřúhelník.
Vezmeme kovexní obal (covex hull) těchto pěti bodů. (i) Pokud je to pětiúhelník -> jakékoliv 4 dělají konvexní čtyřúhelník. (ii) Pokud je to čtyřúhelník, tak ty čtyři na okraji Předpokládejme tedy že obal je trojúhelník. Ostatní dva body nemůžou ležet na jeho okraji (obecná poloha), ale uvnitř.
Vezmeme tedy jeden a postavíme 6 částí jako na obrázku. Podle toho v jaké části leží vybereme zbývající dva vrcholy trojúhelníku společně s a máme hotovo. opět nemůže ležet mezi částmi, kvůli obecné poloze.
Pro , jakákoliv mnozina bodů v rovině v obecné poloze obsahuje alespoň bodů tvořící konvexní čtyřúhelník.
Pořídíme si množinu bodů v rovině. V ní obarvíme všechny čtveřice tak, že
- , tak netvoří konvexní čtyřúhelník
- , tak tvoří konvexní čtyřúhelník
Množství bodů (Ramseyovo číslo) nám teď říká, že:
- existuje pětice taková, že každá čtveřice z pětice má barvu 1 NEBO
- existuje t-tice taková, že každá čtveřize z t-tice má barvu 2.
První případ se nemůže stát, je to přímá negace Happy-ending problému. Takže určitě existuje nějaká t-tice , ve které . Vezměme konvexní obal této . Pokud má t vrcholů, tak jsme vyhráli. Pokud má měné než t vrcholů, tak existuje nějaký vrchol , co je uvnitř. To znamená že existují nějaké body které tvoří trojúhelník ve kterém je uzavřeno.
Tato čtveřice bodů ale netvoří čtyřúhelník, což je spor, protože mají barvu 2.
Error-correcting codes
[P: chapter 8]
Motivační příklad. Pojďme si posílat zprávy. Komunikační linka je ale nestabilní a mění nám znaky za jiné. Chtěli bychom za málo poslaných znaků navíc dokázat opravit co nejvíce takto změněných znaků.
Pro jednoduchost pojďme posílat bity. Náš jazyk má tedy pouze dva znaky. Abychom, dokázali opravit nějakou chybu, každý bit co pošleme ztrojíme. Místo “1101” pošleme “111111000111”. Jakýkoliv změněný bit dokážeme opravit, protože druhé dva ve trojici zůstanou nezměněny. Pokud ale někdo změní dva bity, můžeme mít smůlu a kód opravit špatně.
- abeceda (alphabet) je konečná množina znaků - abeceda často bude nějaké konečné těleso, nejčastěji
- slovo délky je seznam (nebo řádkový vektor) znaků z abecedy
- je množina všech slov délky z abecedy
- kód je podmnožina .
- prvky kódu jsou codewords, for the lack of neat translation
Je to jednoduše počet rozdílných znaků ve dvou slovech. Formálně Rozmysli si, že je to metrika na .
Je definovaná jako počet “nenulových” znaků, nebo Hammingova vzdálenost od nulového vektoru.
Jak se tyto primitivy používají?
S je odesílatel, R je přijímač. S i R znají nějakou bijekci mezi všemy kódy a všemi možnými zprávami. Je to bijekce, tedy množina kódů a všech zpráv jsou stejně velké. Všechny zprávy budou tipicky kratší než n, jinak by to byl docela naprd kód.
S tedy vezme zprávu, přeloží ji na kód a pošle R. R zprávu přijme, možná s nějakými chybami. Opraví ji a pomocí ji přeloží zpátky na zprávu.
Předpokládejme abecedu o alespoň dvou znacích a C je kód s alespoň dvěma codewords. Tento kód má pak nějaké parametry.
- = délka slov v
- = velikost abecedy ()
- = velikost je , užitečnější ale bude logaritmus o základu q.
- = minimální vzdálenost v ()
To nám dává kód. Rozmysli si, kolik dokážeme v takovém kódu opravit chyb.
řešení
Příklady kódů. Náš opakující se kód ze začátku byl , kde n je “činitel” (slova jsou roznásobené znaky). Slova jsou dlouhá , to si můžeme zvolit jak chceme. Množina kódů je stejně velká jako abeceda, protože akorát vezme každý znak z abecedy a dá ho krát za sebou. je tedy 1, protože je to . Minimální vzdálenost bude přesně , protože každá dvě slova jsou kompletně jiná.
Rozmysli si, co je za kód co nic nedělá. Pouze pošle slovo nad nějakou abecedou velikosti délky . Nijak ho nepřeloží.
Hint: je zadané, -> kolik je ? minimální vzdálenost dvou kódů.
Řešení: . To protože kódů je - jsou to všechny zprávy. Vzdálenost dvou kódů je malá, pouze 1.
Parity code. a naše kódy budou mít vždy součet nad . Tento kód bude kód. , prvních znaků si můžeme vybrat a poslední určíme tak, aby byl součet co nejmenší. . Vzdálenost je 2, protože dva kódy nemůžou mít vzdálenost 1, to by znamenalo že jeden z nich má součet .
Teďka se řeší nějaký boundy na to, jak velký můžou bejt ty množiny kódů (jakoby ), když nám někdo zadá n,d,q. Upřímně doufám že to ommitne protože to sou fakt hovna xd.
ommited by Džanek, read up on [P 8.3]
Lineární kód je podprostor prostoru . Pokud je to také kód, tak se píše do hranatých závorek, je totiž důležitej :)
Těmi kódy co posíláme jsou opravdu myšleny vektory toho podprostoru. Čím větší si vezmu, tím má větší dimenzi a tím se mi zvětšuje . Ale kvůli tomu bude menší . Ještě existuje pojem generator matrix - to jsou bazické vektory nasázené do sloupce. Z toho se dá vyrobit parity check - to je taky matice, ale tentokrát báze kolmých vektorů.
Vynásobením lze jednoduše ověřit, jestli do C patří, či nikoliv.
Pokud je an -kód, tak
Pořiďme si . jsou bazické vektory . je nyní složené z lineárních kombinací těchto vektorů . Pro každé máme možností jak si vybrat (protože ). Jelikož jsou vektory lineárně nezávislé, tak je celkem různých kódů.
Z toho 🔲
Pokud je - kód s , tak
wt je Hammming weight - vzdálenost od 0.
Zafixujeme s nejmenší hammingovskou váhou. Dokazujeme že .
Jelikož je kód ve kterém je 0 i x, tak z definice d - je nejmenší takové. V také existují různé vektory , jejichž . Jelikož je podprostor, tak . Tudíž - to víme protože x je nejmenší takové.
Celkově . Složením nerovností 🔲.
Když fixneme a tak musí být small.
(wait je tohle hamming code?)
$C sube Z_2^n je pak .
Pro každé jukni na kouli . Protože má , žádné 2 koule se nepřekrývají.
(slova, slova … důkaz že se nepřekrývají)
pak protože velikost prostoru je a je volume koule a pokud se nepřekrývají tak něco něco
Gilbert-Varnshmdr Bound
and
Zdroje
- I. Penev: Combinatorics and Graph Theory 1 & 2
- J. Matoušek, J. Nešetřil: Invitation to discrete mathematics, 2nd edition, 2008 👈 tenhle je fakt good
- Tomáš Sláma (goat)
- the voices in my head
uuuuwwwiieee