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: Mgr. 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: prof. 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.