The bandwidth theorem for locally dense graphs
18th December 2018, 11:00 am – 12:00 pm
Howard House, 4th Floor Seminar Room
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).