Local resilience of spanning subgraphs in sparse random graphs

For each real γ>0 and integers δ≥2 and k≥1, we prove that there exist constants β>0 and C>0 such that for all p≥C(logn/n)1/δ the random graph G(n, p) asymptotically almost surely contains - even after an adversary deletes an arbitrary (1/k-γ)-fraction of the edges at every vertex - a copy of every n-vertex graph with maximum degree at most δ, bandwidth at most βn and at least Cmaxp-2, p-1logn vertices not in triangles.

Subjects

Extremal graph theory

Random graphs

Resilience

Sparse regularity

DDC Class

510: Mathematik

Options

Local resilience of spanning subgraphs in sparse random graphs