Local Resilience for Containment of Bounded Degree Spanning Subgraphs

Source abstract

We prove that for all $Δ\geq 2$ and $γ> 0$, there exists a constant $C = C(Δ, γ)$ such that for $p\geq C(\log n/n)^{1/Δ}$, asymptotically almost surely, every spanning subgraph $G$ of $G(n,p)$ with minimum degree at least $(1-1/(2Δ)+γ)pn$ contains every $n$-vertex graph $H$ with maximum degree at most $Δ$ and with at least $Cp^{-2}$ vertices not in any triangles of $H$. This is a 'sparse local resilience version' of a classical theorem of Sauer and Spencer. The condition that $H$ should contain some vertices not in triangles is necessary, and in fact, the quantity $p^{-2}$ is asymptotically best possible. A key feature of our result is that $H$ is allowed to be an expander graph, distinguishing it from previous results of similar nature, which dealt with, e.g., graphs of sublinear bandwidth. Our proof makes use of regularity arguments, with the sparse blow-up lemma for random graphs being a key tool.