Original title: Postačující podmínky pro vnořování stromů
Translated title: Sufficient conditions for embedding trees
Authors: Rozhoň, Václav ; Klimošová, Tereza (advisor) ; Dvořák, Zdeněk (referee)
Document type: Bachelor's theses
Year: 2018
Language: eng
Abstract: [eng] [cze]
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 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
Keywords: Erdős-Sós conjecture; extremal graph theory; Loebl-Komlós-Sós conjecture; regularity lemma; tree embedding; domněnka Erdős-Sósové; domněnka Loebl-Komlós-Sósové; extrémální teorie grafů; regularity lemma; vnořování stromů

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/99784

Permalink: http://www.nusl.cz/ntk/nusl-383950


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses