Original title: Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Translated title: Szemerédi Regularity Lemma a jeho aplikace v kombinatorice
Authors: Hladký, Jan ; Kráľ, Daniel (advisor) ; Dvořák, Zdeněk (referee)
Document type: Master’s theses
Year: 2008
Language: eng
Abstract: [eng] [cze]
In the thesis we provide a solution of the Loebl-Komlós-Sós Conjecture (1995) for dense graphs. We prove that for any q > 0 there exists a number n0 N such that for any n > n0 and k > qn the following holds. Let G be a graph of order n with at least n/2 vertices of degree at least k. Then any tree of order k+1 is a subgraph of G. This improves previous results by Zhao (2002), and Piguet and Stein (2007). A strengthened version of the above theorem together with a lower bound for the problem is discussed. As a corollary a tight bound on the Ramsey number of two trees is stated. The proof of the main theorem combines a Regularity-Lemma based embedding technique with the Stability Method of Simonovits. Results presented here are based on joint work with Diana Piguet. V práci podáme důkaz domněnky Loebla, Komlóse a Sósové (1995) pro husté grafy. Dokážeme následující tvrzení. Pro libovolné q > 0 existuje číslo n0 takové, že pokud má libovolný graf G řadu n > n0 alespoň polovinu vrcholů se stupněm alespoň k > qn, pak G obsahuje každý strom na k+1 vrcholech jako podgraf. Tím vylepšujeme předchozí výsledky autorů Zhao (2002) a Piguet a Stein (2007). Ukážeme, že v jistých případech lze předpoklady věty oslabit. Je diskutována dolní mez k problému. Jako důsledek hlavní věty dostaneme těsný odhad Ramseyova čísla dvou stromů. Důkaz hlavní věty kombinuje vnořovací techniku založenou na Regularity Lemmatu s Metodou stability. Výsledku bylo dosaženo ve společné práci s Dianou Piguet.

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/17805

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


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