A spanning bandwidth theorem in random graphs

Journal
Combinatorics, probability & computing  
Volume
31
Issue
4
Start Page
598
End Page
628
Citation
Combinatorics Probability and Computing 31 (4) : 598-628 (2022)
Publisher DOI
10.1017/S0963548321000481
Scopus ID
2-s2.0-85121215887
Publisher
Cambridge Univ. Press
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.
Subjects
random graphs
spanning subgraphs
sparse regularity