Szemerédi Regularity Lemma a jeho aplikace v kombinatorice

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