Přednáška z Kombinatoriky a grafů II 2020/21

Přednáším Kombinatoriku a grafy 2 (NDMI012) každé pondělí v 15:40.

Pokud máte dotaz, který můžete vznést veřejně, nejlepší prostor je OWL. Pokud vám nepřišel enrollment token, napište mi email. Pokud máte soukromý dotaz, napište mi email na adresu koutecky@iuuk.mff.cuni.cz a do předmětu uveďte text [KG2]. Až bude probíhat výuka osobně, jste též vítáni v mé pracovně S326.

Další materiály doplním v průběhu semestru.

datum	co se přednášelo [zdroj]
1. 3.	Edmondsův algoritmus pro hledání největšího párování [T, VM, Sh] záznam. Jak jít na ekvivalenci „($G$ má $M$-zlepšující cestu $\Leftrightarrow$ $G.C$ má $M.C$-zlepšující cestu“? [VM] na to jdou myslím zbytečně složitě; lepší je dokázat si pomocné tvrzení, že můžu přealternovat hrany na stonku a tím dostat kytku bez stonku a pak se případy rozeberou jednodušeji. To dělá [T], ale ten mi přijde, že to zjednodušuje příliš. Asi nejvíc se mi líbí popis v [Sh].
8. 3.	Tutteova věta o perfektním párování [VM], Petersenova věta ($2$-souvislý $3$-regulární graf má PP) [D], záznam
15. 3.	Tutteova charakterizace 3-souvislých grafů [VM Lemma 7.2; D Thm 3.2.5], minory, Kuratowského věta [VM kap. 7; D Chp 4], záznam
22. 3.	Dokončení Kuratowského věty ($2$-souvislé grafy mají stěny ohraničeny kružnicemi: [D Prop 4.2.6]; graf má $K_5$ nebo $K_{3,3}$ jako minor právě když je má jako podrozdělení: [D Lemma 4.4.2]; $3$-souvislý případ Kuratowského věty je [D Lemma 4.4.3]; alternativně [VM 7], ale není tam skoro vůbec rozebrané, proč když nenastanou 2 špatné případy už musí být všichni sousedé $y$ obsažení v segmentu mezi dvěma po sobě jdoucími sousedy $x$ na hranici relevantní stěny…), úvod do grafů na plochách [Dv1, MT 3, R 3-4], záznam
29. 3.	Zobecněná Eulerova formule, Heawoodova formule [Dv1, Dv2, R 4] záznam
12. 4.	Brooksova věta [Dv2] záznam
19. 4.	Vizingova věta [Dv2] animace Tomáše Slámy, perfektní grafy [D] animace Tomáše Slámy, záznam, ; Lemma o nafouknutí vrcholu je [D Lemma 5.5.4]
26. 4.	Chordální grafy [Ba, D, HR], Bondy-Chvátalova věta [BCh], záznam
3. 5.	Tutteův polynom, jeho rekurentní vztahy pro mazání a kontrakce. Chromatický polynom, jeho vyjádření pomocí Tutteova polynomu [Bo]. záznam
10. 5.	Úvod do formálních mocninných řad a obyčejných vytvořujících funkcí [W], záznam Bohužel záznam se přerušil před koncem – chybí v něm ještě interpretace $1 + H(x) + H(x)^2 + … = 1/(1-H(x))$ jakožto funkce, kde koeficient u $x^n$ určuje počet konečných posloupností hlavních jídel s cenou přesně n Kč. Zde se používá substituce $y=H(x)$ do výrazu $1/(1-x)$ a proto vyžadujeme, aby $[x^0]H(x) = 0$, tzn. aby neexistovalo žádné jídlo zdarma. To dává smysl, protože pokud je nějaké jídlo zdarma, tak např. posloupností za 0 Kč je nekonečně mnoho.
17. 5.	Exponenciální vytvořující funkce [W], akce grupy – základní pojmy [Bo], záznam
24. 5.	Burnsiderovo lemma a jeho aplikace [Bo] záznam
31. 5.	Extremální teorie grafů a hypergrafů – Turánova věta [D], grafy se zakázaným $K_r$ minorem mají lineárně mnoho hran [D], Erdos-Ko-Rado věta. [EKR], záznam

Podoba zkoušky a okruhy

Užitečné zdroje KG2

Sbírka úloh
Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
[Sh] A. Shoemaker: Edmonds' Blossom Algorithm (notes)
[T] R. Tarjan Sketchy notes on [...] blossom algorithm for general matching
[VM] T. Valla, J. Matoušek: Kombinatorika a grafy I
[P] J. Plank: Edmonds' General Matching Algorithm Lecture Notes
[Ba] P. Bartlett: Chordal graphs (zápisky z přednášky)
[Bo] B. Bollobás: Modern Graph Theory
[BCh] The Bondy and Chvátal Theorem
[D] R. Diestel: Graph Theory
[DT] Dilworth theorem: perfection of comparability graphs
[Dv1] Z. Dvořák: Prezentace o kreslení grafů na plochy, poznámky o kreslení na plochy
[MT] B. Mohar, C. Thomassen: Graphs on Surfaces
[Dv2] Z. Dvořák: Prezentace o Brooksově a Vizingově větě, poznámky
[EKR] The Erdős-Ko-Rado theorem
[HR] Y. Haimovitch, A. Raviv: Chordal graphs (ppt prezentace)
[W] H. Wilf: Generatingfunctionology
[R] G. Ringel: Map Color Theorem