Kombinatorika a grafy I

V letním semestru 2013/2014 přednáším Kombinatoriku a grafy I [NDMI011]. Přednáška se koná každý pátek od 9:00 v S3.

datum co se přednášelo [zdroj]
21. 2. Asymptotické odhady funkcí. Motivační příklad s doplňky rovinných grafů. Odhady faktoriálu: e(n/e)n ≤ n! ≤ en(n/e)n, vylepšení na n! ≤ en1/2(n/e)n, zmínka o Stirlingově formuli. Odhady kombinačních čísel: (n/k)k ≤ C(n,k) ≤ (ne/k)k. "Jak je vysoký hroznýš?" – odhady prostředního kombinačního čísla: 2n/(n+1) ≤ C(n,n/2) ≤ 2n, 4m/2m1/2 ≤ C(2m,m) ≤ 4m/(2m)1/2. [K 3.4–3.5]
28. 2. Hrátky s násobením polynomů a binomickou větou. Vytvořující funkce a základní operace s nimi (sčítání, násobení, derivování, integrování, dosazování), zmínka o konvegrenci mocninných řad. Prefixové součty (F(x)/(1-x)). Odvození vztahu pro n-té Fibonacciho číslo (rozklad na parciální zlomky). [K 12.1–12.3]
7. 3. Pokračování vytvořujících funkcí. Zobecněná binomická věta. Lemmátko o C(-a,b). Počítání binárních stromů na n vrcholech, Catalanova čísla. Věta o řešení lineárních rekurencí pro případ bez násobných kořenů. [K 12.3–12.4, LR]
14. 3. Konečné projektivní roviny: definice a základní vlastnosti, dualita. Algebraická konstrukce. Obecněji o množinových systémech, jejich incidenčních grafech a dualitě. [K 9.1–9.2]
21. 3. Latinské čtverce a jejich ortogonalita, souvislost s projektivními rovinami. Systémy různých reprezentantů a Hallova věta. Grafová verze Hallovy věty (perfektní párování v bipartitních grafech). [K 9.3, D]
28. 3. Přednáška se přesouvá na 4. 4. od 10:40.
4. 4. Birkhoffova věta o bistochastických maticích [D].
Toky v sítích: základní definice, rezervy hran a (ne)nasycené cesty, Fordův-Fulkersonův algoritmus pro hledání maximálního toku a důkaz jeho korektnosti pomocí řezů. Minimaxová věta o maximálním toku a minimálním řezu. Celočíselné sítě mají celočíselný maximální tok. Příklad sítě s reálnými kapacitami, na které se F-F algoritmus nezastaví a ani nekonverguje k maximálnímu toku (detaily konstrukce nezkouším) [S 2.1–2.3]. Náznak důkazu existence maximálního toku přes kompaktnost [S 2.5]. F-F algoritmus s volbou nejkratší nenasycené cesty je efektivní [D].
11. 4. Vztah mezi párováními v bipartitních grafech a celočíselnými toky, důkaz Hallovy věty pomocí toků [S 4]. Vrcholová a hranová souvislost grafů. Odebráním hrany se ke i kv buď zachová nebo sníží o 1. Charakterizace souvislosti pomocí disjunktních cest: Fordova-Fulkersonova a Mengerova věta. [S 3]
18. 4. Důkaz Mengerovy věty [S 3]. Důsledek: kv ≤ ke ≤ δ. Syntéza 2-souvislých grafů dělením hran, případně přidáváním uší [K 4.7]. Počítání koster úplného grafu pomocí „povykosů“ [K 8.1, 8.6].
25. 4. Kirchhoffova věta: počet koster libovolného grafu pomocí determinantu Laplaceovy matice [K 8.5] (pozor, důkaz z přednášky najdete jen v novějších vydáních Kapitol). Počítání koster rekurencemi, příklad pro vějíř.
2. 5. Extremální kombinatorika: maximální počet hran grafu bez trojúhelníků a bez čtyřcyklů, dolní odhad pomocí konečných projektivních rovin [K 4.8, 7.3, 9.4]. Cauchyho-Schwarzova nerovnost [K 7.3]. Úvod do Ramseyovy teorie: příklad s večírkem, Ramseyova věta pro grafy [K 11.1, 11.2].
9. 5. Ramseyovy věty: princip holubníku (jinak též Dirichletův), Ramseyova věta pro grafy a její vícebarevná verze. Dolní odhad na Ramseyova čísla pravděpodobnostní metodou. Důkaz Ramseyovy věty pro nekonečné (spočetné) grafy a jeho úprava pro konečný případ. Ramseyova věta pro p-tice, zatím pouze v nekonečné verzi. [K 11.3, S 1, R]
16. 5. Přednáška se přesouvá na 23. 5. od 10:40.
23. 5. Nekonečná Ramseyova věta implikuje konečnou [R]. Erdősova-Szekeresova věta o bodech v konvexní poloze [S]. Schurova věta o součtech. Spernerova věta o nezávislém systému množin [K 7.2]. Základy teorie kódů: úvodní příklad s Fanovou rovinou, kódy a jejich parametry, Hammingova metrika, kódová vzdálenost a její souvislost s detekcí a opravou chyb. Singletonův odhad. Lineární kódy obecně a třída Hammingových kódů. Zmínka o perfektních kódech. [T 1, 3.1, 3.3, 4.1, věta 4.4.1]

Cvičení

Druhou českou paralelku vede Ondřej Pangrác, anglickou vede Zdeněk Dvořák. Přednášky jsou téměř synchronní, takže si můžete vybrat kterékoliv cvičení ke kterékoliv přednášce.

Zkoušky

Zkouškové termíny budou během celého zkouškového období, přihlašujte se, prosím, v SISu. Ke zkoušce je potřeba zápočet, znalost odpřednesené látky (definic, vět, důkazů) a schopnost ji aplikovat (tj. řešit příklady podobné těm z cvičení). Doporučena jest čistá mysl a dobrá nálada.

Příklady ze všech zkouškových termínů zapisuji do Sbírky příkladů.

Literatura

Stránku spravuje Martin Mareš