Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Limity diskrétních struktur

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
D01LDS ZK 2 2P česky
Garant předmětu:
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra matematiky
Anotace:

Předmět se věnuje prezentaci moderních metod diskrétní matematiky jež se soustředí na úvod do teorie grafových limit, kterou systematicky vybudovali autoři okolo Lazslo Lovásze, a velmi úzce související tzv. lemma o regularitě objevené Endré Szemerédim. Tato témata patří k nejzásadnějším objevům v matematice posledních desetiletí, což je mimojiné doloženo řadou významných matematických cen udělených za tyto objevy, včetně Abelovy ceny, kterou oba tito vědci za svou práci získali (Szemerédi v roce 2012, Lovász v roce 2021). Krom systematické prezentace teorie grafových limit bude též kladen důraz na její použití v jiných oblastech matematiky, jako např. Alon-Shapirova věta o sublinéarním testování vlastností, Szemerédiho řešení Erdős–Turánovy doměnky o aritmetických posloupnostech, či zodpovězení otázky Chatterjee-Varadhana týkající se tzv. principu velkých odchylek v náhodných grafech.

Požadavky:
Osnova přednášek:

1. Grafové homomorfismy, grafové algebry

2. Szemerédiho regularity lemma a jeho aplikace

3. Sublineární testování vlastností v informatice

4. Řezová metrika, reprezentace grafové limity analytickou funkcí (grafon)

5. Konvergence zleva a počítání podgrafů

6. Zobecněné barvení a konvergence zprava

7. Entropie grafonu, princip velkých odchylek

8. Semidefinitní programování, flag algebry

9. Teorie hypergrafových limit, teorie limit turnajů, teorie permutačních limit

Osnova cvičení:
Cíle studia:
Studijní materiály:

Povinná literatura:

[1] L. Lovász: Large Networks and Graph Limits, American Mathematical Society, 2012.

Doporučená literatura:

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

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

Poznámka:
Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 16. 6. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7948806.html