Spanning embeddings of arrangeable graphs with sublinear bandwidth1. Issue 2 (7th July 2015)

• Record Type: Journal Article
• Authors: Böttcher, Julia; Taraz, Anusch; Würfl, Andreas
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 270
• Page End: 289
• Publication Date: 2015-07-07
• Subjects: graph embedding -- bandwidth theorem -- arrangeable graphs -- Ramsey numbersregularity method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20593
• Languages: English
• ISSNs: 1042-9832

Abstract

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