Embedding trees in sparse graphs

Diana Piguet

University of Birmingham

Abstract

Many problems in extremal graph theory are solved using Szemeredi's regularity Lemma. The method is standard, well understood and follows the following pattern. We approximate the graph with a simpler graph using the regularity lemma, find a suitable combinatorial structure in this simpler graph and solve the problem using this structure. However, Szemeredi's regularity lemma is of no help when the underlying graph is sparse. This area of extremal graph theory (dealing with sparse graphs) have raised much interest during the last years.

During the talk I shall expose a technique for embedding trees in sparse graphs. It is a counterpart of the regularity lemma for sparse graphs: it decomposes the graph into vertices of huge degree, regular pairs and two more parts which exhibit certain expansion properties. Recently, with Hladky, Komlos, Simonovits, Stein and Szemeredi we used this technique to solve the