Témata prací (Výběr práce)Témata prací (Výběr práce)(verze: 336)
Detail práce
  
Number of faces in a random embedding of a complete graph
Název práce v češtině: Počty stěn v náhodném nakreslení úplného grafu
Název v anglickém jazyce: Number of faces in a random embedding of a complete graph
Klíčová slova: graf|nakreslení
Klíčová slova anglicky: graph|embedding
Akademický rok vypsání: 2020/2021
Typ práce: bakalářská práce
Jazyk práce: angličtina
Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
Vedoucí / školitel: doc. Mgr. Robert Šámal, Ph.D.
Řešitel: Bc. David Ryzák - zadáno a potvrzeno stud. odd.
Datum přihlášení: 16.04.2021
Datum zadání: 16.04.2021
Datum potvrzení stud. oddělením: 11.06.2021
Datum a čas obhajoby: 02.09.2021 08:00
Datum odevzdání elektronické podoby:22.07.2021
Datum odevzdání tištěné podoby:22.07.2021
Datum proběhlé obhajoby: 02.09.2021
Oponenti: doc. RNDr. Martin Tancer, Ph.D.
 
 
 
Zásady pro vypracování
Je dobře známo [MT, W1] že nakreslení grafu na plochu lze popsat (až na homeomorfismus) pomocí lokálních rotací -- seznamu cyklických permutací, z nichž každá popisuje pořadí hran incidentních s jedním z vrcholů. V 90. letech začali Stahl [S] a White [W2] zkoumat, co se stane, když lokální rotace vybereme náhodně. Parametry nakreslení (počty stěn různých délek, rod plochy) se stanou náhodnými proměnnými a začnou být důležité ne konkrétní hodnoty, ale celé rozdělení. Tato oblast matematiky se ukazuje být důležitá mj. pro teoretickou fyziku [LZ].

Hypotéza Mauka a Stahla [MS] říká, že střední hodnota počtu stěn nakreslení náhodného grafu je 2 log(n). Úkolem studenta bude prozkoumat související otázky: jaká je střední hodnota počtu stěn dané velikosti? Jaké je rozdělení příslušné náhodné proměnné? (Se zaměřením na krátké stěny.) Zkoumání bude probíhat jak pomocí statistického testování experimentálně získaných dat, tak pomocí teoretického rozboru.
Seznam odborné literatury
[LZ] Sergei K. Lando, Alexander K. Zvonkin: Graphs on surfaces and their applications, Springer-Verlag, Berlin, 2004.
[MT] Bojan Mohar, Carsten Thomassen: Graphs on surfaces. Johns Hopkins University Press, Baltimore, MD, 2001.
[MS] Clay Mauk, Saul Stahl: Cubic graphs whose average number of regions is small. Discrete Mathematics, 159(1-3):285–290, 1996.
[S] Saul Stahl: On the average genus of the random graph. J. Graph Theory, 20(1):1–18, 1995.
[W1] Arthur T. White: Graphs, groups and surfaces. North-Holland, Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973.
[W2] Arthur T. White: An introduction to random topological graph theory. Combin. Probab.Comput., 3(4):545–555, 1994.
 
Univerzita Karlova | Informační systém UK