Embedding trees into graphs

Graphs, Hypergraphs, and Computing

13 February 15:30 - 16:30

Miklos Simonovits - Alfred Renyi Institute of Mathematics

Extremal graph theory is one of the important, deep and fast developing areas in Discrete Mathematics. In my lecture I will consider two famous Turan type extremal graph conjectures: I will speak of the exact solution of the Erdos-T. Sos and Komlos-Sos conjectures.

The first part is a joint work with M. Ajtai, J. Komlos, and E. Szemeredi, the second part with Maya Stein, Jan Hladky, Janos Komlos, Diana Piguet, and Endre Szemeredi.

The main result is that both conjectures hold for large trees. I will sketch the proof of the Erdos-Sos and the Loebl-Komlos-Sos conjectures, asserting that if either the average degree of a graph G_n or the median degree of a graph is large, then every k-vertex tree T_k is embeddable into this graph.

The proofs are extremely long, I will try to sketch the main lines of the proof of the Erdos-Sos conjecture. My lecture is related to that of Jan Hladky, though does not assume attending that lecture.
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