Back to Search Start Over

A spanning bandwidth theorem in random graphs

Authors :
Allen, Peter
Böttcher, Julia
Ehrenmüller, Julia
Schnitzer, Jakob
Taraz, Anusch
Publication Year :
2019

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 $Cp^{-2}$ vertices should not be in triangles.<br />Comment: 26 pages. arXiv admin note: text overlap with arXiv:1612.00661

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1911.03958
Document Type :
Working Paper