A spanning bandwidth theorem in random graphs

Source abstract

Abstract The bandwidth theorem of Böttcher, Schacht and Taraz states that any n -vertex graph G with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)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 $p\gg \big(\tfrac{\log n}{n}\big)^{1/\Delta}$ a.a.s. each spanning subgraph G of G ( n , p ) with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)pn$ contains all n -vertex k -colourable graphs H with maximum degree $\Delta$ , bandwidth o ( n ), and at least $C p^{-2}$ 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 $K_\Delta$ then we can drop the restriction on H that $Cp^{-2}$ vertices should not be in triangles.