velikost textu

Sufficient conditions for embedding trees

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Sufficient conditions for embedding trees
Název v češtině:
Postačující podmínky pro vnořování stromů
Typ:
Bakalářská práce
Autor:
Bc. Václav Rozhoň
Vedoucí:
Mgr. Tereza Klimošová, Ph.D.
Oponent:
doc. Mgr. Zdeněk Dvořák, Ph.D.
Konzultant:
Mgr. Diana Piguetová, Ph.D.
Id práce:
194375
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (B1801)
Obor studia:
Obecná informatika (IOI)
Přidělovaný titul:
Bc.
Datum obhajoby:
22. 6. 2018
Výsledek obhajoby:
Výborně
Jazyk práce:
Angličtina
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 v angličtině:
extremal graph theory, tree embedding, Loebl-Komlós-Sós conjecture, Erdős-Sós conjecture, regularity lemma
Abstrakt:
Studujeme podmínky na stupně vrcholů, které vynucují, že daný graf obsahuje libovolný strom z dané třídy. Tento typ problémů zahrnuje některé známé problémy z oblasti extremální teorie grafů. Nejslavnějším z nich je domněnka Erdős-Sósové, která tvrdí, že každý graf s průměrným stupněm vyšším než k − 1 obsahuje libovolný strom na k + 1 vrcholech. Naše dva hlavní výsledky jsou následující. Dokazujeme přibližnou verzi domněnky Erdős-Sósové pro husté grafy a stromy se sublineárním maximál- ním stupněm. Dále studujeme přirozené zobecnění domněnky Loebl-Komlós- Sósové a opět dokážeme přibližnou verzi této domněnky pro husté grafy. Oba výsledky jsou založeny na takzvané regularity metodě. Druhý výsledek je společnou prací s T. Klimošovou a D. Piguet. 1
Abstract v angličtině:
We study sufficient degree conditions that force a host graph to contain a given class of trees. This setting involves some well-known problems from the area of extremal graph theory. The most famous one is the Erdős-Sós conjecture that asserts that every graph with average degree greater than k − 1 contains any tree on k + 1 vertices. Our two main results are the following. We prove an approximate version of the Erdős-Sós conjecture for dense graphs and trees with sublinear max- imum degree. We also study a natural refinement of the Loebl-Komlós-Sós conjecture and prove it is approximately true for dense graphs. Both results are based on the so-called regularity method. The second mentioned result is a joint work with T. Klimošová and D. Piguet. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Václav Rozhoň 819 kB
Stáhnout Abstrakt v českém jazyce Bc. Václav Rozhoň 43 kB
Stáhnout Abstrakt anglicky Bc. Václav Rozhoň 42 kB
Stáhnout Posudek vedoucího Mgr. Tereza Klimošová, Ph.D. 57 kB
Stáhnout Posudek oponenta doc. Mgr. Zdeněk Dvořák, Ph.D. 41 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Jiří Fiala, Ph.D. 154 kB