Embedding spanning subgraphs via degree sequence conditions

Andrew Treglown

University of Birmingham

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