Allen, PeterPeterAllenBöttcher, JuliaJuliaBöttcherEhrenmüller, JuliaJuliaEhrenmüllerSchnitzer, JakobJakobSchnitzerTaraz, AnuschAnuschTaraz2022-01-062022-01-062022Combinatorics Probability and Computing 31 (4) : 598-628 (2022)http://hdl.handle.net/11420/11418The 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.en1469-216320224598628Cambridge Univ. Pressrandom graphsspanning subgraphssparse regularityJournal Article10.1017/S0963548321000481Journal Article