Sylabus
Dvojí počítání: Spernerova věta, Maximální počet hran grafu bez C4 a bez K3.
Počet koster grafu.
Vytvořující funkce (chápané jako Taylorovy řady), aplikace: Catalanova, Fibonacciho čísla, řešení rekurenci, asymptotika rekurencí.
Konečné projektivní roviny.
Samoopravné kódy, základní pojmy. Hammnigův kód, Hadamardův kód. Existence asymptoticky dobrých kódů (Gilbert-Varshamov). Hammingův dolní odhad.
Maximální párování v grafech, Hallova věta a aplikace (Birkhoff-von Neumannova věta), Tutteho věta. k-souvislost, Mengerovy věty. Ušaté lemma, struktura 2-souvislých grafů.
Základní Ramseyovy věty, Ramseyova věta pro p-tice, nekonečná Ramseyova věta.
Königova věta o nekonečné větvi.
Anotace
Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.