The bandwidth theorem for locally dense graphs

Abstract

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 of bandwidth $o(n)$, thereby proving a conjecture of Bollobás and Komlós. 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.

35 pages. Author accepted version, to appear in Forum of Mathematics, Sigma