pith. sign in

arxiv: 1305.2078 · v1 · pith:MS7C2OWQnew · submitted 2013-05-09 · 🧮 math.CO

Spanning embeddings of arrangeable graphs with sublinear bandwidth

classification 🧮 math.CO
keywords graphsbandwidthdegreealmostminimumnumberplanarresult
0
0 comments X
read the original abstract

The Bandwidth Theorem of B\"ottcher, 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 \Delta(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+\gamma)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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.