Combinatorics Seminar

When: Sunday, February 25, 10am Where: Schreiber 309 Speaker: Julia Boettcher, TU Munchen Title: On spanning subgraphs of dense graphs

Abstract:

A conjecture by Bollobas and Komlos states the following: For every gamma>0 and integers r>=2 and Delta, there exists beta>0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least (gamma+(r-1)/r)n and H is an r-chromatic graph with n vertices, bandwidth at most (beta n) and maximum degree at most Delta, then G contains a copy of H. This conjecture generalizes several results concerning sufficient degree conditions for the containment of spanning subgraphs. We recently proved this conjecture.

In the talk I will give an introduction to the problem and an overview of previous results, I will sketch our proof and outline some ideas about future work.

A joint work with Mathias Schacht and Anusch Taraz.