Jan Hladky: Loebl-Komlos-Sos Conjecture and embedding trees in sparse graphs

We prove an approximate version of the Loebl-Komlos-Sos Conjecture which asserts that if half of the vertices of a graph G have degrees at least k then G contains each tree T of order k+1 as a subgraph.

The proof of our result follows a strategy common to approaches which employ the Szemeredi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we use a general decomposition technique (a variant of which was introduced by Ajtai, Komlos, Simonovits and Szemeredi to resolve to Erdos-Sos conjecture) which applies also to sparse graphs: each graph can be decomposed into vertices of huge degree, regular pairs (in the sense of the Regularity Lemma), and an expander-like part.

Joint work with Janos Komlos, Diana Piguet, Miki Simonovits, and Endre Szemeredi.