Kombinatorika a grafy II

Přednáška v pátek 10:40, S3

• 5. 10. (přednáška odpadla, látka se místo toho probírala na cvičeních) hledání největšího párování, opakování Hallovy věty,  Edmondsův algoritmus
• 12. 10. Tutteova věta o existenci perfektního párování
• 19. 10. Lemma o kontrahovatelné hraně ve 3-souvislém grafu, Tutteova charakterizace 3-souvislých grafů, definice minoru, třídy uzavřené na minory a jejich charakterizace pomocí minimálních zakázaných minorů, zmínka o tom, že minimálních zakázaných minorů je konečně mnoho, Kuratowského věta a Wagnerova věta.
  
• 26. 10. Plochy: jejich generování pomocí křížítek a uší, rod plochy, Eulerova charakteristika. Eulerova formule pro plochy, důsledky pro odhad počtu hran a průměrný stupeň grafu nakresleného na ploše.
  
• 2. 11. Důkaz Eulerovy formule (pro orientovatelné plochy), odhad na degenerovanost grafů nakreslitelných na danou plochu, Heawoodova formule. Brooksova věta.
• 9. 11. Perfektní grafy, slabá věta o perfektních grafech.
• 16. 11. Chordální grafy: jejich ekvivalentní charakterizace pomocí xy-řezů, pomocí simpliciálních vrcholů, pomocí perfektního eliminačního schématu a také (bez důkazu) pomocí průnikových grafů podstromů ve stromě. Důkaz, že chordální grafy jsou perfektní.
• 23. 11. Hranová barevnost grafů, Vizingova věta. Tutteho polynom, a jeho charakterizace pomocí mazání a kontrakcí.
• 30. 11.  Výpočet počtu obarvení pomocí Tutteho polynomu. Postačující podmínky pro existenci hamiltonovské kružnice: Bondyho-Chvátalova věta, Oreho věta, Diracova věta.
  
• 7. 12. Formální mocninné řady, operace s nimi: sčítání, násobení, existence a jednoznačnost multiplikativní inverze, formální derivace, skládání mocninných řad. Kombinatorické třídy, kombinatorické třídy s parametry, jejich součiny a mocniny, obyčejné vytvořující funkce a kombinatorický význam operací s nimi. Labelované kombinatorické třídy, jejich exponenciální vytvořující funkce.
• 14. 12. Operace s exponenciálními vytvořujícími funkcemi a odpovídající konstrukce pro labelované třídy: labelovaný součin, k-tá mocnina, třídy Set_k(A) a Set(A). Akce grup na množinách; základní pojmy grupových akcí: orbita, stabilizátor, množina pevných bodů.
• 21. 12. Burnsideovo lemma, aplikace na počítání náhrdelníků a tříd izomorfismu.
• 4. 1. Turánova věta. Věta o tom, že grafy bez zakázaného minoru mají omezený průměrný stupeň. Erdős-Ko-Radoova věta.
  
• 11. 1. Věta o slunečnici. Připomenutí konečné a nekonečné Ramseyovy věty pro p-tice. Princip kompaktnosti. Kanonická Ramseyova věta pro dvojice.