Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Pokročilá teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
01PTG ZK 2 2P+0C česky
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: 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ů:
Platnost dat k 27. 5. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7850806.html