|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (vedoucí práce) ; Dvořák, Zdeněk (oponent)
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
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Keevash, Peter (oponent) ; Krivelevich, Michael (oponent)
disertační práce Structural graph theory Jan Hladký V práci se zabýváme domněnkou Loebla, Komlóse a Sósové, která je kla- sickým problémem extremální teorie grafů. Dokážeme následující slabou verzi domněnky: pro libovolné α > 0 existuje číslo k0 takové, že pro každé k > k0 a každý n-vrcholový graf G obsahující alespoň (1 2 + α)n vrcholů stupně ale- spoň (1 + α)k platí, že G obsahuje každý strom T na k vrcholech jako podgraf. Důkaz tohoto výsledku sleduje strategii běžnou v přístupech využívajících Szemerédiho regularity lemma: nejdřív je graf G rozložen a v tomto rozkladu je nalezena kombinatorická struktura s vhodnými vlastnostmi. V posledním kroku je strom T vnořen do G pomocí této struktury. Rozklad zaručený původním regularity lemmatem je ovšem triviálni pokud je G řídký. Abychom obešli toto omezení, vyvineme rozkladovou techniku která umožňuje postihnout i strukturu řídkých grafů: každý graf může být rozložen do vrcholů s velkým stupněm, regulárních párů (ve smyslu regularity lemmatu) a dvou dalších částí, které mají jisté expandující vlastnosti. Výsledky v této práci byly dosaženy s následujícími spolupracovníky: János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein,...
|
|
|
Sufficient conditions for embedding trees
Rozhoň, Václav ; Klimošová, Tereza (vedoucí práce) ; Dvořák, Zdeněk (oponent)
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
|
|
|
Structural Graph Theory
Hladký, Jan ; Kráľ, Daniel (vedoucí práce) ; Keevash, Peter (oponent) ; Krivelevich, Michael (oponent)
disertační práce Structural graph theory Jan Hladký V práci se zabýváme domněnkou Loebla, Komlóse a Sósové, která je kla- sickým problémem extremální teorie grafů. Dokážeme následující slabou verzi domněnky: pro libovolné α > 0 existuje číslo k0 takové, že pro každé k > k0 a každý n-vrcholový graf G obsahující alespoň (1 2 + α)n vrcholů stupně ale- spoň (1 + α)k platí, že G obsahuje každý strom T na k vrcholech jako podgraf. Důkaz tohoto výsledku sleduje strategii běžnou v přístupech využívajících Szemerédiho regularity lemma: nejdřív je graf G rozložen a v tomto rozkladu je nalezena kombinatorická struktura s vhodnými vlastnostmi. V posledním kroku je strom T vnořen do G pomocí této struktury. Rozklad zaručený původním regularity lemmatem je ovšem triviálni pokud je G řídký. Abychom obešli toto omezení, vyvineme rozkladovou techniku která umožňuje postihnout i strukturu řídkých grafů: každý graf může být rozložen do vrcholů s velkým stupněm, regulárních párů (ve smyslu regularity lemmatu) a dvou dalších částí, které mají jisté expandující vlastnosti. Výsledky v této práci byly dosaženy s následujícími spolupracovníky: János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein,...
|
host ::
RSS.