Pokročilá teorie grafů

Vztahy:

Podmínkou zápisu na předmět 01PTG je, že student v některém z předchozích semestrů úspěšně absolvoval předmět 01TG

Garant předmětu:

Jan Volec

Přednášející:

Jan Volec

Cvičící:

Předmět zajišťuje:

katedra matematiky

Anotace:

Obsahem předmětu je výklad pokročilých témat z teorie grafů, jakými jsou např. Szemerédiho lemma o regularitě, Lovászovo lokální lemma, aplikace koncentračních nerovností (Azuma-Hoeffding, Talagrand),

polyhedrální kombinatorika, řešení Dinitzova problému, aplikace metod lineární algebry v kombinatorice.

Požadavky:

Osnova přednášek:

1. Submodularita hranových řezů, Gomory-Hu stromy.

2. Edmondsův algoritmus pro perfektní párování, Christofidesův aproximační algoritmus pro problém obchodního cestujícího.

3. Vybíravost grafu: Thomassenova věta, Alonova věta, Galvinovo řešení Dinitzova problému.

4. Erdős-Pósova vlastnost pro cykly v grafech.

5. Perfektní grafy, Lovászova slabá věta o perfektních grafech.

6. Aplikace lineární algebry v kombinatorice: Sudo-licho města, existence Mooreových grafů.

7. Koncentrační nerovnosti a jejich aplikace: protipříklad Hajósově doměnce, průměrný stupeň vs. úplný minor, velikost komponent souvislosti náhodného grafu.

8. Lovászovo lokální lemma a jeho aplikace: Ramseyova čísla, acyklické obarvení grafu, silné chromatické číslo grafu.

9. Szemerédiho lemma o regularitě a jeho aplikace v kombinatorice: RuzsaSzemerédiho (6,3)-problém, odebírací lemmata, Rothova věta o aritmetických posloupnostech délky 3, Erdős-Stoneova věta.

Osnova cvičení:

Cíle studia:

Studijní materiály:

[1] N. Alon, J. Spencer: The Probabilistic Method, Wiley, 2016.

[2] J. A. Bondy, U.S.R. Murty: Graph Theory, Springer-Verlag, 2008.

[3] Y. Zhao: Graph Theory and Additive Combinatorics, Cambridge University Press, 2023.

Poznámka:

Další informace:

http://honza.ucw.cz/PTG

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů: