On spanning subgraphs of dense and not so dense graphs

Abstract:

One of the fundamental results in extremal graph theory is the theorem by Erd"os and Stone which implies that any fixed graph H of chromatic number r is forced to appear as a subgraph in any sufficiently large graph G on n vertices if the average degree of G is at least ((r-2)/(r-1)+gamma)n for an arbitrarily small but positive constant gamma. Bollobas and Komlos conjectured an analogue of this theorem for spanning subgraphs H which we proved recently. This result implies for example that any sufficiently large graph on n vertices with minimum degree at least (3/4+gamma)n contains all bounded degree planar graphs on n vertices as subgraphs.

In the talk we will introduce the problem, sketch its history and some consequences, discuss different variations of the topic, and try to outline what is known about problems of this type when the graph G is sparser but a so-called pseudo-random graph.

This is based on joint work with Klaas Pruessmann, Mathias Schacht, Anusch Taraz, and Andreas Wuerfl.