Sufficient conditions for embedding trees
Thesis title in Czech: | Postačující podmínky pro vnořování stromů |
---|---|
Thesis title in English: | Sufficient conditions for embedding trees |
Key words: | extrémální teorie grafů, vnořování stromů, domněnka Loebl-Komlós-Sósové, domněnka Erdős-Sósové, regularity lemma |
English key words: | extremal graph theory, tree embedding, Loebl-Komlós-Sós conjecture, Erdős-Sós conjecture, regularity lemma |
Academic year of topic announcement: | 2017/2018 |
Thesis type: | Bachelor's thesis |
Thesis language: | angličtina |
Department: | Department of Applied Mathematics (32-KAM) |
Supervisor: | Mgr. Tereza Klimošová, Ph.D. |
Author: | hidden![]() |
Date of registration: | 27.09.2017 |
Date of assignment: | 05.10.2017 |
Confirmed by Study dept. on: | 03.11.2017 |
Date and time of defence: | 22.06.2018 10:00 |
Date of electronic submission: | 16.05.2018 |
Date of submission of printed version: | 18.05.2018 |
Date of proceeded defence: | 22.06.2018 |
Opponents: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
Advisors: | Mgr. Diana Piguet, Ph.D. |
Guidelines |
Cílem práce je studium postačujících podmínek pro vnoření stromu do grafu a získání nových poznatků v této oblasti.
Student se seznámí několika domněnkami týkajícími se podmínek pro vnoření stromu (Erdős-Sósové, Loebl-Komlós-Sósové a Havet-Reed-Stein-Woodovou), s existujícími částečnými výsledky a s metodami použitými k jejich dosažení. Tyto metody se pokusí aplikovat k důkazu slabších variant uvedených domněnek - například s pozměněnými podmínkami pro vnoření či pro speciální typy stromů. |
References |
F. Havet, B. Reed, M. Stein, D. R. Wood: A Variant of the Erdős-Sós Conjecture. arXiv:1606.09343 (2016)
D. Piguet and M. J. Stein: An approximate version of the Loebl-Komlós-Sós conjecture. J. Combin. Theory Ser. B, 102(1):102–125 (2012). D. Piguet and M. Stein: The Loebl-Komlós-Sós conjecture for trees of diameter 5 and certain caterpillars. Electronic Journal of Combinatorics, 15 (2008), R106. A další odborná literatura dle doporučení vedoucí a konzultantky. |