Kombinatorika a grafy I

V letním semestru 2009/2010 přednáším Kombinatoriku a grafy I [NDMI011]. Přednáška se koná každý pátek od 10:40 v S5.

datum co se přednášelo [zdroj]
26. 2. Asymptotické odhady funkcí. Motivační příklad s doplňky rovinných grafů. Odhady faktoriálu: nn/2 ≤ n! ≤ ((n+1)/2)n, e(n/e)n ≤ n! ≤ en(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. Úkol: Odhad C(2m,m) pomocí Stirlingovy formule. [K 3.4 – 3.5]
5. 3. Princip inkluze a exkluze a dva jeho důkazy (počítáním a algebraicky pomocí charakteristických funkcí množin). Problém šatnářky aneb počet permutací bez pevného bodu. Počet surjektivních zobrazení, souvislost s počítáním ekvivalencí a Stirlingovými čísly. [K 3.6 – 3.7]
12. 3. Hrátky s násobením polynomů. 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. Odvození vztahu pro n-té Fibonacciho číslo (rozklad na parciální zlomky). [K 12.1 – 12.3]
19. 3. Pokračování vytvořujících funkcí. Zobecněná binomická věta. Prefixové součty (F(x)/(1-x)). 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í, důkaz pro případ bez násobných kořenů pomocí lineární algebry. [K 12.3 – 12.4, LR]
26. 3. Konečné projektivní roviny: definice a základní vlastnosti, dualita. Algebraická konstrukce. (Přednášel kolega Pangrác.) [K 9.1 – 9.2]
2. 4. Latinské čtverce a jejich ortogonalita, souvislost s projektivními rovinami. Obecněji o množinových systémech, jejich incidenčních grafech a dualitě. Systémy různých reprezentantů a Hallova věta. [K 9.3, D]
9. 4. Grafová verze Hallovy věty a její důsledky. Doplňování latinských obdélníků na latinské čtverce. 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. [S 2.1 – 2.3]
16. 4. Pokračování toků v sítích: důkaz korektnosti F-F algoritmu, minimaxová věta, existence maximálního toku. Příklad sítě s iracionálními kapacitami, na které se F-F algoritmus nezastaví a ani nekonverguje k maximálnímu toku. [S 2.1 – 2.3, 2.5]
23. 4. Vztah mezi párováními v bipartitních grafech a celočíselnými toky, důkaz Hallovy věty pomocí toků. Vrcholová a hranová souvislost grafů. Lemma: odebráním hrany se ke i kv buď zachová nebo sníží o 1. Věta: kv ≤ ke. [S 3, 4]
30. 4. Charakterizace souvislosti pomocí disjunktních cest: Fordova-Fulkersonova a Mengerova věta. Syntéza 2-souvislých grafů dělením hran, případně přidáváním uší. [S 3, K 4.7]
7. 5. Věta o skóre. Počítání dvěma způsoby: grafy bez C4, Spernerova věta o nezávislém systému množin, počet koster grafu Kn bez jedné hrany. [K 4.4, 7.2 – 7.3]
14. 5. Ramseyovy věty: princip holubníku (jinak též Dirichletův), Ramseyova věta pro grafy a její barevná verze, Ramseyova věta pro p-tice. Dolní odhad na Ramseyova čísla pravděpodobnostní metodou. [K 11, S 1]
21. 5. Birkhoffova věta o bistochastických maticích. Malá ochutnávka nekonečné kombinatoriky: důkaz Cantorovy-Bernsteinovy věty pomocí nekonečných grafů, Königova věta o nekonečných stromech, věta o kompaktnosti výrokové logiky a její použití na barvení spočetných grafů. [D]

Cvičení

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

Stránky mého cvičení.

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ů.

Vypsal jsem i dva záchranné termíny v září, opět viz SIS.

Literatura

Stránku spravuje Martin Mareš