Almost spanning subgraphs of random graphs after adversarial edge removal
Böttcher, Julia
; Kohayakawa, Yoshiharu; and Taraz, Anusch
(2013)
Almost spanning subgraphs of random graphs after adversarial edge removal.
Combinatorics, Probability and Computing, 22 (5).
pp. 639-683.
ISSN 0963-5483
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.
| Item Type | Article |
|---|---|
| Departments | Mathematics |
| DOI | 10.1017/S0963548313000199 |
| Date Deposited | 12 Aug 2013 11:02 |
| URI | https://researchonline.lse.ac.uk/id/eprint/45822 |
ORCID: https://orcid.org/0000-0002-4104-3635