The bandwidth theorem for locally dense graphs. (4th November 2020)

• Record Type: Journal Article
• Authors: Staden, Katherine; Treglown, Andrew
• Is Part Of: Forum of mathematics. Volume 8(2020)
• Publication Date: 2020-11-04
• Subjects: 05C35; bandwidth, -- embedding, -- regularity method; Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2020.39
• Languages: English
• ISSNs: 2050-5094

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.