Miklos Simonovits: Embedding trees into graphs
Time: Thu 2014-02-13 15.30 - 16.30
Location: Institut Mittag-Leffler, Auravägen 17, Djursholm
Participating: 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.