1 results
The bandwidth theorem for locally dense graphs
- Part of
-
- Journal:
- Forum of Mathematics, Sigma / Volume 8 / 2020
- Published online by Cambridge University Press:
- 04 November 2020, e42
-
- Article
-
- You have access
- Open access
- Export citation
-
The bandwidth theorem of Böttcher, Schacht, and Taraz [Proof of the bandwidth conjecture of Bollobás andKomló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.
