Sufficient conditions for embedding trees
| Název práce v češtině: | Postačující podmínky pro vnořování stromů |
|---|---|
| Název v anglickém jazyce: | Sufficient conditions for embedding trees |
| Klíčová slova: | extrémální teorie grafů, vnořování stromů, domněnka Loebl-Komlós-Sósové, domněnka Erdős-Sósové, regularity lemma |
| Klíčová slova anglicky: | extremal graph theory, tree embedding, Loebl-Komlós-Sós conjecture, Erdős-Sós conjecture, regularity lemma |
| Akademický rok vypsání: | 2017/2018 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra aplikované matematiky (32-KAM) |
| Vedoucí / školitel: | Mgr. Tereza Klimošová, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 27.09.2017 |
| Datum zadání: | 05.10.2017 |
| Datum potvrzení stud. oddělením: | 03.11.2017 |
| Datum a čas obhajoby: | 22.06.2018 10:00 |
| Datum odevzdání elektronické podoby: | 16.05.2018 |
| Datum odevzdání tištěné podoby: | 18.05.2018 |
| Datum proběhlé obhajoby: | 22.06.2018 |
| Oponenti: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Konzultanti: | Mgr. Diana Piguet, Ph.D. |
| Zásady pro vypracování |
| 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ů. |
| Seznam odborné literatury |
| 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. |