Spanning embeddings of arrangeable graphs with sublinear bandwidth

The Bandwidth Theorem of Böttcher, Schacht and Taraz [Mathematische Annalen 343 (1), 175-205] gives minimum degree conditions for the containment of spanning graphs H with small bandwidth and bounded maximum degree. We generalise this result to a-arrangeable graphs H with Δ(H)<sqrt(n)/log(n), where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least (3/4+γ)n contain almost all planar graphs on n vertices as subgraphs. Using techniques developed by Allen, Brightwell and Skokan [Combinatorica, to appear] we can also apply our methods to show that almost all planar graphs H have Ramsey number at most 12|H|. We obtain corresponding results for graphs embeddable on different orientable surfaces.

No reviews yet.

No comments yet.