2019/11/06 by Allen, Peter, Böttcher, Julia, Ehrenmüller, Julia +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.03958
The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any n-vertex graph G with minimum degree ((k-1)/(k)+o(1))n contains all n-vertex k-colourable graphs H with bounded maximum degree and bandwidth o(n). In [arXiv:1612.00661] a random graph analogue of this statement is proved: for p≫ ((log n)/(n))1/Δ a.a.s. each spanning subgraph G of G(n,p) with minimum degree ((k-1)/(k)+o(1))pn contains all n-vertex k-colourable graphs H with maximum degree Δ, 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Δ then we can drop the restriction on H that Cp-2 vertices should not be in triangles.