Katherine Staden

The bandwidth theorem for locally dense graphs

The bandwidth theorem of Böttcher, Schacht and Taraz gives a condition on the minimum degree of an n-vertex graph G that ensures G contains every r-chromatic graph H on n vertices of bounded degree and bandwidth o(n), thereby proving a conjecture of Bollobás and Komlós. I will discuss a version of the bandwidth theorem for locally dense graphs. This is the statement that every locally dense n-vertex graph G with δ(G) > (1/2 + o(1))n contains as a subgraph any given (spanning) H with bounded chromatic number and maximum degree, and sublinear bandwidth.

This is joint work with Andrew Treglown (Birmingham).