Kombinatorika a grafy I - NDMI011 (LS 2015/16)

přednášející V. Jelínek

Přednáška se koná ve středu od 12:20 v S9.

• 24. 2.: Odhady na důležité funkce: n!, n nad k, 2n nad n.
• 2. 3.: Vytvořující funkce: motivace a základní vlastnosti mocninných řad, zobecněná kombinační čísla a zobecněná binomická věta, odvození vytvořující funkce rekurentně zadané posloupnosti.
• 9. 3.: Racionální funkce, jejich rozklad na parciální zlomky, použití parciálních zlomků při počítání koeficientů mocninných řad. Catalanova čísla, definovaná jako počet binárních stromů s n vnitřními vrcholy, odvození jejich vytvořující funkce a vzorečku pro n-té Catalanovo číslo.
• 16. 3.: Projektivní roviny. Dualita, graf incidence. Vlastnosti konečné projektivní roviny řádu n.
  
• 23. 3.: Ortogonalita latinských čtverců, odhad na maximální počet ortogonálních latinských čtverců řádu n. Souvislost s existencí konečné projektivní roviny řádu n. Toky v sítích: věta o tom, že tok je maximáľní, právě když nemá zlepšující cestu, což je právě když existuje řez, který má stejnou velikost.
• 30. 3.: Kőnigova - Egerváryho věta o největším párování a nejmenším vrcholovém pokrytí v bipartitním grafu. Hallova věta o systému různých reprezentantů v hypergrafu, její souvislost s párováními v bipartitních grafech.
• 6. 4.: Hranová a vrcholová k-souvislost grafu, Mengerovy věty pro hranovou a vrcholovou souvislost.
• 13. 4.: Lemma o uších pro vrcholově 2-souvislé grafy. Počítání dvěma způsoby: Cayleyho vzorec pro počet koster úplného grafu. Důsledek pro počet koster úplného grafu bez jedné hrany.
• 20. 4.: Spernerova věta. Odhad na počet hran v grafech bez kružnice délky 4 a bez kružnice délky 3.
• 27. 4.: Ramseyovy věty pro grafy, včetně verze pro barvení hran úplného grafu pomocí více barev.
• 4. 5.: Přednáška odpadla - rektorský den.
• 11. 5.: Nekonečná a konečná verze Ramseyovy věty pro barvení p-prvkových množin. Kőnigovo lemma pro nekonečné stromy.
• 18. 5.: Úvod do samoopravných kódů, základní pojmy: Hammingova vzdálenost, (n,k,d)-kód, lieární kód, generující matice a její použití ke kódování, kontrolní matice.
• 25. 5.: Souvislost mezi minimální vzdáleností kódu a jeho kontrolní maticí. Hammingovy kódy: jejich parametry a dekódování. Hadamardovy kódy: jejich parametry. Singletonův, Hammingův a Gilbertův-Varshamovův odhad na parametry kódů.
  

Doporučená literatura:

• J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky, Karolinum 2000 (dotisk 2002, 2007 a 2009, předchozí vydání MatfyzPress 1996). Ve starším vydání knihy je několik chyb, pozor na ně.
• Skriptíčka T. Vally a J. Matouška, ke stažení zde.
• Učební text T. Kaisera k přednášce o samoopravných kódech, ke stažení zde.
  

Cvičení a zápočty: Informace o zápočtech se dozvíte od svých cvičících.

Zkoušky: Přihlašování pomocí SISu, termíny tamtéž.