| Anotace: | Evoluční teorie grafů je mladý obor na pomezí matematické biologie a teoretické
informatiky, který studuje jisté náhodné procesy, které modelují, jak se věci
šíří po grafech (sítích). Každý vrchol grafu má jednu z typicky dvou barev,
které proti sobě "bojují" tak, že náhodné vrcholy náhodně přebarvují své sousedy
na svou barvu až dokud jedna barva "nevyhraje". Klíčové otázky jsou určit
pravděpodobnost výhry jednotlivých barev a čas, jak dlouho bude souboj průměrně
trvat, v závislosti na tom, jak vypadá graf a počáteční obarvení jeho vrcholů.
V přednášce si ukážeme některé elegantní výsledky z oboru, jako například
Isotermální větu [Nature '05], FPRAS pro pravděpodobnost fixace na neorientovaných
grafech [SODA '14] nebo existenci rychlých superamplifikátorů [Nat.Comm '21].
Prerekvizity: alespoň základy teorie grafů (vrchol, hrana, stupeň) a alespoň
intuitivní chápání pojmu pravděpodobnost.
|
|---|