The bandwidth theorem for locally dense graphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Oxford

Abstract

The Bandwidth theorem of B¨ottcher, Schacht and Taraz [Proof of the bandwidth conjecture of Bollob´as and Koml´os, 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´as and Koml´os [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 δ(G) > (1/2 + o(1))n contains as a subgraph any given (spanning) H with bounded maximum degree and sublinear bandwidth.

Details

Original languageEnglish
Article numbere42
Number of pages36
JournalForum of Mathematics, Sigma
Volume8
Publication statusPublished - 4 Nov 2020

Keywords

  • bandwidth, embedding, regularity method