Almost spanning subgraphs of random graphs after adversarial edge removal
Böttcher, J.
, Kohayakawa, Y. & Taraz, A.
(2013).
Almost spanning subgraphs of random graphs after adversarial edge removal.
Combinatorics, Probability and Computing,
22(5), 639-683.
https://doi.org/10.1017/S0963548313000199
, Kohayakawa, Y. & Taraz, A.
(2013).
Almost spanning subgraphs of random graphs after adversarial edge removal.
Combinatorics, Probability and Computing,
22(5), 639-683.
https://doi.org/10.1017/S0963548313000199
Let Δ ≥ 2 be a fixed integer. We show that the random graph ${\mathcal{G}_{n,p}}$ with $p\gg (\log n/n)^{1/\Delta}$ is robust with respect to the containment of almost spanning bipartite graphs H with maximum degree Δ and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges from ${\mathcal{G}_{n,p}}$ in such a way that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all such H.