The bandwidth theorem for locally dense graphs

Abstract

Abstract The bandwidth theorem of Böttcher, Schacht, and Taraz [ Proof of the bandwidth conjecture of Bollobás and Komlós, Mathematische Annalen, 2009 ] 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 of bandwidth $o(n)$ , thereby proving a conjecture of Bollobás and Komlós [ The Blow-up Lemma, Combinatorics, Probability, and Computing, 1999 ]. In this paper, we prove a version of the bandwidth theorem for locally dense graphs. Indeed, we prove that every locally dense n -vertex graph G with $\delta (G)> (1/2+o(1))n$ contains as a subgraph any given (spanning) H with bounded maximum degree and sublinear bandwidth.