Embedding spanning subgraphs via degree sequence conditions

Andrew Treglown (University of Birmingham)

When: November 3, 2pm

Where: room G2.91b

Abstract

A graph H on n vertices has bandwidth at most b if there exists a labelling of the vertices of H by the numbers 1,…,n such that for every edge ij of H, |i-j| is at most b. Boettcher, Schacht and Taraz gave a condition on the minimum degree of a graph G on n vertices that ensures G contains every r-chromatic graph H on n vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture of Bollobás and Komlós. We strengthen this result in the case when H is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph G on n vertices that forces G to contain every bipartite graph H on n vertices of bounded degree and of bandwidth o(n). This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on G is relaxed to a certain robust expansion property. This is joint work with Fiachra Knox. (I will also mention related joint work with Daniela Kuehn and Deryk Osthus, and work with József Balogh and Alexandr Kostochka.)