A spanning bandwidth theorem in random graphs

Abstract

The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$-vertex graph $G$ with minimum degree $(\frac{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\gg (\frac{\log n}{n}{)}^{1/\Delta }$ a.a.s. each spanning subgraph $G$ of $G(n,p)$ with minimum degree $(\frac{k-1}{k}+o(1))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 $C{p}^{-2}$ vertices should not be in triangles.

26 pages. arXiv admin note: text overlap with arXiv:1612.00661