The Loebl-Komlos-Sos conjecture states that if a graph has at least half its vertices with
degree at least k than any tree with at most k edges embeds in G. We proved an approximative version of
this conjecture, i. e. for any small positive pi and q there exists a number n_0 such that any graph G on
n=> n_0 vertices, satisfying that at least (1+pi) n/2 of its vertices have degree at least (1+pi)qn,
contains as a subgraph any tree with at most qn edges.
We prove this theorem using Szemeredi regularity lemma, partitioning the tree into small subtrees and
suitably embedding those into regular pairs of clusters of high density.
This is a joint work with Maya Stein.