Přednáška z Kombinatoriky a grafů 2 v LS 22/23

středa 12:20 v S4

Stránka přednášky Pavla Veselého z Kombinatoriky a grafů 2 (KG2), která probíhá v LS 22/23 každou středu od 12:20 v učebně S4. Budeme navazovat na přednášku z KG1 Martina Balka. Představu o přednášce si můžete udělat z loňské přednášky Víta Jelínka a předloňské přednášky Martina Kouteckého.

Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po přednášce. Také budu rád, když se během přednášky budete ptát, jakmile vám nebude něco jasné. Chcete-li konzultaci, ozvěte se mi emailem nebo po přednášce (vhodný čas může být po přednášce). Můžete mě též najít v kanceláři S326 v budově na Malé Straně (v chodbě KAM/IUUK ve 3. patře, zhruba naproti učebně S3), ale je lepší se ozvat předem.

K záznamům: vzhledem k nedeterministickým technickým problémům (v polovině případů nefunkční mikrofon v Zoomu) jsem se rozhodl dále přednášky nenahrávat. Budu zveřejňovat poznámky a nabízím možnost konzultací, pokud jste zameškali kvůli nemoci či plánované cestě. Dále je možné se látku naučit z literatury níže (důkazy, definice či značení se mohou lišit, při zkoušce nebudu vyžadovat své definice, důkazy a značení, ale musíte vědět, co které značení a pojem znamená)

Co jsme dělali / plán

U každého tématu jsou odkazy na literaturu níže. Občas používám tuto (průběžně doplňovanou) prezentaci.

1. 15. 2. Edmondsův algoritmus pro hledání největšího párování.
Pracovní poznámky a záznam (tabule jsou přiblížené po cca 21 minutách, popř. lze paralelně koukat do poznámek).
Další zdroje: [VM] (sekce 5.2; značení podobné jako na přednášce), [P] (sekce 9.5-9.7), [Sh] (poměrně dobrý popis algoritmu i analýzy) a [T] (stručný text, ale obsahuje to hlavní)
2. 22. 2. Zaskočil Vít Jelínek: Tutteova charakterizace grafů s perfektním párováním (s důkazem) a Petersenova věta o 3-reguárních grafech bez mostů (důkaz pomocí Tutteovy charakterizace byl na cvičeních).
Zdroje: [VM] (sekce 5.1), [P] (kapitola 9) a [D] (sekce 2.2)
3. 1. 3. Tutteova charakterizace 3-souvislých grafů, úvod grafových minorů a topologických minorů. Charakterizace rovinných grafů: Kuratowského-Wagnerova věta (zatím bez důkazu hlavní implikace).
Poznámky. Záznam se bohužel podařilo pořídit.
Další zdroje: [VM] (sekce 7), [P] (sekce 10.1 a 10.2) a [D] (kapitola 4)
4. 8. 3. Důkaz Kuratowského-Wagnerovy věty (hlavní implikace). Úvod do kreslení grafů na plochy.
Poznámky a prezentace (s obrázky z Wikipedie a od Z. Dvořáka). Záznam se bohužel opět nepodařilo pořídit.
Zdroje k plochám: [P] (kap. 11), [Dv] (poznámky k plochám), [MT] (kapitola 3) a [R] (kapitoly 3-4)
Pár videí: projektivní rovina a Möbiova páska, Kleinova láhev, a dvojitý torus.
5. 15. 3. Kreslení grafů na plochy: vytváření pomocí přidávání uší a křížítek, zobecněná Eulerova formule a Heawoodovo číslo (důkaz barevnosti bude dokončen příště).
Poznámky a záznam.
Zdroje k plochám podobné jako minule: [P] (kap. 11), [Dv] (poznámky k plochám a poznámky k Heawood číslu), [MT] (kapitola 3 a sekce 8.3)
6. 22. 3. Dokončení kreslení grafů na plochy (viz slajd 9 v prezentaci, Věta 2 bez důkazu). Brooksova věta o vrcholovém barvení a Vizingova věta o hranovém barvení (důkaz bude dokončen příště).
Poznámky k barvení.
Zdroje k barvení: [Dv] (poznámky k barvení), [P] (kap. 12), [D] (část kapitoly 5)
7. 29. 3. Dokončení důkazu Vizingovy věta o hranovém barvení (viz poznámky a zdroje minule). Zpět k vrcholovému barvení: Mycielskiho konstrukce grafů bez trojúhelníkům a s libovolně velkou vrcholovou barevností (dle [P] 13.1). Úvod do perfektních grafů, příklady a znění silné a slabé věty o perfektních grafech (důkaz slabé bude příště, důkaz silné si můžete v případě zájmu přečíst v původním článku).
Poznámky k perfektním grafům.
Zdroje k perfektním grafům: [Dv] (poznámky k perfektním grafů), [P] (kap. 14), [D] (sekce 5.5)
Videa od Tomáše Slámy: Vizingova věta a perfektní věty (včetně důkazu slabé věty).
8. 5. 4. Perfektní grafy: důkaz slabé věty o perfektních grafech. Chordální grafy: definice, lemma o minimálním řezu a věta o charakterizaci přes existenci simpliciálních vrcholů (perfektní eliminační schéma jsme nestihli).
Poznámky k perfektním grafům a k chordálním grafům (z nich jsme stihli necelé první dvě strany).
Zdroje k chordálním grafům: [Dv] (poznámky k chordálním grafů), [P] (sekce 13.3) a [Ba]
9. 12. 4. Chordální grafy: zmínka o perfektním eliminačním schématu (s důkazy bude na cvičení). Grafové polynomy: chromatický polynom (počítání dobrých k-obarvení) a polynom spolehlivosti a jejich rekurentní vzorce. Tutteův polynom jako jejich zobecnění: definice přes rank a nulitu, multiplikativní vlastnost a rekurentní vzorec. Chromatický polynom jako speciální případ Tutteova (bez důkazu).
Poznámky ke grafovým polynomům.
Zdroje ke grafovým polynomům: [Dv] (poznámky ke grafovým polynomům), [P] (kap. 15) a [Bo]
10. 19. 4. Opakování obyčejných vytvořujících funkcí a formálních mocninných řad (včetně operací s nimi a významu násobení) a ukázka použití pro asymptotický odhad počtu objektů přes poloměr konvergence. Exponenciální vytvořující funkce, operace s nimi a význam násobení. Příklad s počtem zakořeněných koster.
Pracovní poznámky.
Zdroje k vytvořujícím funkcím: [Dv] (poznámky k vytvořujícím funkcím), [P] (kap. 2 a 18) a [W] (celá kniha o vytvořujících funkcích)
11. 26. 4. Počítání objektů až na symetrie (např. pozice v deskové hře): "Burnsideovo" lemma včetně obecné verze.
Pracovní poznámky (důkaz lemmatu o orbitě a stabilizátoru má trochu jiné značení a organizaci než na tabuli).
Zdroje: [Dv] (poznámky k Burnsideovu lemmatu), [P] (kap. 17)
12. 3. 5. Zaskočil Zdeněk Dvořák: Extremální kombinatorika: Turánova věta, Erdösova-Ko-Radova věta, a Erdösova-Szekeresova věta (dle poznámek).
Další zdroje: [P] (kap. 19, Erdöse-Szekerese najdete v kap. 7), [D]
- 10. 5. Plán: sportovní aktivity (Rektorský den)
13. 17. 5. Extremální kombinatorika: Slunečnicové lemma (důkaz pro k-uniformní hypergrafy). Hamiltonovské kružnice: Bondyho-Chvátalova věta a Chvátalův uzávěr, Oreho a Diracova věta jako důsledky. Bonus: graf s lichými stupni má buď žádnou Hamiltonovskou kružnici, nebo alespoň tři.
Poznámky.
Slunečnicové lemma zhruba dle [P] (sekce 19.3), Hamiltonovské kružnice dle [Dv] (poznámky k Hamiltonovským kružnicím), jsou popsané i v [P] (kap. 16)

Cvičení

Cvičení k této přednášce vedou:

Zkouška

Zkouška bude ústní s písemnou přípravou. Náhodně vám vyberu dva ze zkušebních okruhů/příkladů, jeden "větší" a jeden "menší", jeden navíc si pak vyberete sami. Je potřeba znát (a chápat) definice a důležitá lemmata a věty a umět řešit vybrané příklady. Důkazy není potřeba se učit zpaměti, stačí znám (a chápat) jejich hlavní myšlenky. Důkazy můžete předvést i jiné než byly na přednášce.

V září vypíši 1-2 termíny, v případě zájmu se mi ale prosím ozvěte dopředu. Chcete-li zkoušku v průběhu července nebo srpna, ozvěte se emailem a pokusíme se shodnout na datu.

Literatura a zdroje

Většina zdrojů je v angličtině: