A spanning bandwidth theorem in random graphs

The bandwidth theorem of Böttcher, Schacht and Taraz states that any n-vertex graph G with minimum degree <![CDATA[ (k-1k+o(1))n ]]> contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). Recently, a subset of the authors proved a random graph analogue of this statement: for <![CDATA[ p≫ (nn)¹/Δ ]]> a.a.s. each spanning subgraph G of G(n,p) with minimum degree <![CDATA[ (k-1k+o(1))pn ]]> contains all n-vertex k-colourable graphs H with maximum degree <![CDATA[ Δ ]]>, bandwidth o(n), and at least <![CDATA[ C p⁻² ]]> vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper, we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in G contain many copies of <![CDATA[ KΔ ]]> then we can drop the restriction on H that <![CDATA[ Cp⁻² ]]> vertices should not be in triangles.

Content

Subjects

random graphs

spanning subgraphs

sparse regularity