Loebl-Komlos-Sos Conjecture and embedding trees in sparse graphs

Graphs, Hypergraphs, and Computing

21 January 14:00 - 15:00

Jan Hladky - University of Warwick

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to