Limity diskrétních struktur
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ů: