Spanning embeddings of arrangeable graphs with sublinear bandwidth1. Issue 2 (7th July 2015) - Böttcher, Julia; Taraz, Anusch; Würfl, Andreas
Abstract: The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 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 ) ≤ 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, et al. [Combinatorica 33 (2013), 125–160] 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. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 270–289, 2016