|
|
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,...
|
|
|
Vlastnosti síťových centralit
Pokorná, Aneta ; Hartman, David (vedoucí práce) ; Balko, Martin (oponent)
Potřeba porozumět komplexním sítím roste společně s jejich složitostí a mírou závis- losti lidstva na těchto sítích. Síťové centrality pomáhají rozpoznávat klíčové prvky kom- plexních sítí. Mezilehlostní (angl. betweenness) centralita je síťová centralita založená na nejkratších cestách. Přesněji řečeno, příspěvěk dvojice vrcholů u, v vrcholu w ̸= u, v je zlomek nejkratších uv-cest vedoucích vrcholem w. Mezilehlostní centralita je potom součet příspěvků vrcholu w od všech dvojic vrcholů u, v ̸= w. V této práci shrnujeme výsledky o přesných hodnotách mezilehlosti a odhadech na její hodnoty. Dále zlepšu- jeme jeden již existující odhad a formulujeme jeho přesnější znění pro r-regulární grafy. Hlavními přínosy této práce jsou dva výsledky týkající se mezilehlostně uniformních grafů, jejichž vrcholy mají stejnou hodnotu mezilehlosti. Přinášíme důkaz tvrzení, že všechny mezilehlostně uniformní grafy řádu n s maximálním stupněm n − k mají průměr ne- jvýše k, čímž jsme vyřešili domněnku uvedenou v literatuře. Dále dokazujeme tvrzení, že mezilehlostně uniformní grafy neisomorfní cyklům, které jsou zároveň buď vrcholově nebo hranově transitivní, jsou 3-souvislé, čímž jsme částečně vyřešili další domněnku. 1
|
|
|
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.