Diplomov´a Pr´ace Szemerédi Regularity Lemma a Jeho Aplikace V Kombinatorice – (szemerédi Regularity Lemma and Its Applications in Combinatorics) Title: Szemerédi Regularity Lemma and Its Applications in Combinatorics

Content Provider	Semantic Scholar
Author	Král, Daniel
Copyright Year	2008
Abstract	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.
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://kam.mff.cuni.cz/~hladky/mojediplomka.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article