Number of faces in a random embedding of a complete graph
| Thesis title in Czech: | Počty stěn v náhodném nakreslení úplného grafu |
|---|---|
| Thesis title in English: | Number of faces in a random embedding of a complete graph |
| Key words: | graf|nakreslení |
| English key words: | graph|embedding |
| Academic year of topic announcement: | 2020/2021 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | doc. Mgr. Robert Šámal, Ph.D. |
| Author: | Bc. David Ryzák - assigned and confirmed by the Study Dept. |
| Date of registration: | 16.04.2021 |
| Date of assignment: | 16.04.2021 |
| Confirmed by Study dept. on: | 11.06.2021 |
| Date and time of defence: | 02.09.2021 08:00 |
| Date of electronic submission: | 22.07.2021 |
| Date of submission of printed version: | 22.07.2021 |
| Date of proceeded defence: | 02.09.2021 |
| Opponents: | doc. RNDr. Martin Tancer, Ph.D. |
| Guidelines |
| 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. |
| References |
| [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. |