Projects per year
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 nvertex graph G that ensures G contains every rchromatic graph H on n vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture of Bollob´as and Koml´os [The Blowup 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 nvertex graph G with δ(G) > (1/2 + o(1))n contains as a subgraph any given (spanning) H with bounded maximum degree and sublinear bandwidth.
Original language  English 

Article number  e42 
Number of pages  36 
Journal  Forum of Mathematics, Sigma 
Volume  8 
DOIs  
Publication status  Published  4 Nov 2020 
Keywords
 bandwidth
 embedding
 regularity method
Fingerprint
Dive into the research topics of 'The bandwidth theorem for locally dense graphs'. Together they form a unique fingerprint.Projects
 1 Finished

EPSRC Fellowship: Dr Andrew Treglown  Independence in groups, graphs and the integers
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils