Robert Šámal
Kombinatorika a grafy III (NDMI073) 2018/19
Rozsah výuky: ZS 2/2 Zk, Z
Čas přednášky: Pondělí 17:20 S10 -- začínáme 8.10.
Čas cvičení: Pondělí 15:40 S8 -- začínáme 15.10.
Zkouška
Zkouška může mít dvě formy podle vašeho výběru. První je obvyklá ústní zkouška z probrané látky, zkušební termíny jsou vypsány.
Druhá metoda spočívá v domácím řešení obtížnějších příkladů z tohoto seznamu.
Pro stupeň výborně je třeba vyřešit dva ze tří zadaných příkladů, řešení sepsat -- a případné nejasnosti dořešit při ústní konzultaci,
(např. ve vypsaných zkušebních termínech, nebo podle dohody jindy). Přiměřený počet iterací je možný.
Prakticky: sepsané řešení mi prosím pošlete alespoň jeden den před tím, než se sejdeme.
Literatura
- [ZD] Web Zdeňka Dvořáka
- [D] R. Diestel: Graph Theory
- [AS] N.Alon, J.Spencer: Probabilistic method
Probraná témata
Bude průběžně doplňováno ...
- 8.10.2018
-
- Minor -- dvě definice.
- Třídy definované přes zakázané minory.
- Hadwigerova hypotéza (informativně).
- Rozklad pomocí klikových sum.
- Zadání cvičení na příště.
- 15.10.2018
-
- Hadwigerova hypotéza pro malá $k$.
- Klika jako minor grafů s hodně hranami (a důsledek pro Hadwigerovu hypotézu).
- Linkovanost (zatím jen definice).
- Zadání cvičení na příště.
- 22.10.2018
-
- $2k$-souvislost a $K_{4k}$-minor implikují $k$-linkovanost
- Důsledek: $f(k)$-souvislost implikuje $k$-linkovanost, pro vhodné $f$.
- Důsledek: Průměrný stupeň $g(k)$ implikuje dělení $K_k$, pro vhodné $g$.
- Zadání cvičení na příště.
- 29.10.2018
-
- Stromové rozklady: definice, základní vlastnosti.
- Stromová šířka, její monotonie vzhledem k minorům, $tw(K_n) = n-1$.
- Bramble.
- Zadání cvičení na příště.
- 5.11.2018
-
- Třída grafů omezené stromové šířky -- uzavřenost na minory, popis pomocí zakázaných minorů.
- Důkaz věty o dualitě stromové šířky. Závěrečné ověření (že nalezený rozklad funguje) jsme nestihli.
Můžete se podívat na kapitolu 12 knihy Diestel -- Graph Theory (Theorem 12.3.9).
Případně i nové vydání (trochu jinak formulovaný důkaz) přímo
na webu autora.
- Zadání cvičení
- 12.11.2018
-
- Algoritmus na maximální nezávislou množinu ve stromu.
- Algoritmus na maximální nezávislou množinu v grafu s daným stromovým rozkladem.
- Informativně: hledání tw a optimálního stromového rozkladu.
- Stromová šířka a hra cops&robber.
- Informativně: graph minor theorem, Courcelle's theorem, Grid theorem.
- Zadání cvičení
- 19.11.2018
-
Nová kapitola: regularity lemma podle knihy R. Diestela
(kap. 7.4, 7.5).
- Definice $\varepsilon$-regulární pár, $\varepsilon$-regulární rozklad.
- Znění Szemerédiho regularity lemma. (Zatím bez důkazu.)
- Lemma: počet vrcholů s dost velkým počtem sousedů.
- Lemma: pokud je $H$ podgraf grafu regularity, je i podgraf původního grafu. Ilustrace a důkaz pro $H=K_3$. Důkaz pro obecné $H$.
- Zadání cvičení
- 26.11.2018
-
- V náhodných grafech tvoří skoro jistě všechny dost velké množiny regulární pár. Zdroj [ZD], přednáška 11.11.2017
- Aplikace Regularity lemmatu: Erdös-Stoneova věta [D], kap. 7.5 nebo [ZD], 26.10.2015
- removal lemma pro trojúhelníky. [AS], kap. 17.4 (property testing triangle-freeness nebo [ZD], 26.10.2015
- 3.12.2018
-
- Property testing -- algoritmy na obrovských grafech.
- Důkaz Regularity lemma. [AS] kap. 17.3 nebo [D], kap. 7.4.
- Zadání cvičení
- 10.12.2018
-
- Vybíravost (seznamové barvení)
- definice
- úvodní pozorování
- neomezenost pro bipartitní grafy
- rovinné grafy -- vybíravost je alespoň 5
- rovinné grafy -- vybíravost je max. 5
- polynomiální metoda -- Chevalley-Warningova věta s nedokončeným důkazem
- podle poznámek Zd. Dvořáka
- Zadání cvičení
- 17.12.2018
-
- 7.1.2019
-