Kombinatorika a grafy II

Přednáška v úterý 14:00, S3

• 1. 10. Edmondsův algoritmus pro hledání největšího párování [T, VM].
  
• 8. 10. Tutteova věta o existenci perfektních párování [D, VM].
  
• 15. 10. Lemma o kontrahovatelné hraně pro 3-souvislé grafy. Tutteova věta charakterizující 3-souvislé grafy pomocí kontrakcí. Definice grafových minorů. Formulace Kuratowského (a Wagnerovy) věty [D].
• 22. 10. Důkaz Kuratowského věty [D]. Úvod do grafů na plochách: klasifikace ploch, jejich generování pomocí uší a křížítek [Bo, Dv1].
  
• 29. 10. Zobecněná Eulerova formule pro buňková nakreslení. Odhady na počet hran, minimální stupeň a barevnost grafů nakreslitelných na danou plochu [Bo, Dv1].
  
• 5. 11. Brooksova věta, Viznigova věta [D, Dv2]. Pojem perfektního grafu [D].
  
• 12. 11. Slabá věta o perfektních grafech [D].
  
• 19. 11. Chordální grafy: charakterizace pomocí xy-řezů, pomocí existence simpliciálního vrcholu, pomocí existence perfektního eliminačního schématu. Důkaz, že chordální grafy jsou perfektní. Důkaz, že perfektní eliminační schéma lze zkonstruovat hladovým algoritmem v polynomiálním čase [D, Ba, HR].
  
• 26. 11. Tutteův polynom: multiplikativita pro nesouvislé a ne-2-souvislé grafy, ekvivalentní definice pomocí kontrakcí a mazání hran. Souvislost s počtem dobrých obarvení [Bo].
  
• 3. 12. Formální mocninné řady a základní operace s nimi: sčítání, násobení skládání, derivace. Existence převrácené hodnoty. Kombinatorické třídy a jejich obyčejné vytvořující funkce [W].
  
• 10. 12. Exponenciální vytvořující funkce a "labelované" kombinatorické třídy [W]. Základní pojmy týkající se akcí na grupách: orbita, stabilizátor, souvislost mezi jejich velikostmi [Bo].
• 17. 12. Burnsideovo lemma a příklady jeho použití [Bo].
• 7. 1. Turánova věta [D]. Věta o počtu hran v grafu bez úplného minoru [D, v obecnější verzi pro dělení]. Erdős-Ko-Radoova věta [EKR].