Pokročilá teorie grafů
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| 01PTG | ZK | 2 | 2P+0C | česky |
- 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: Ruzsa–Szemeré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 2023/2024:
- Rozvrh není připraven
- Rozvrh na letní semestr 2023/2024:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů: