Local resilience of spanning subgraphs in sparse random graphs
Allen, Peter
; Böttcher, Julia
; Ehrenmüller, Julia; and Taraz, Anusch
(2015)
Local resilience of spanning subgraphs in sparse random graphs.
In: European Conference on Combinatorics, Graph Theory and Applications, 2015-08-31 - 2015-09-04, Bergen,Norway,NOR.
(Submitted)
For each real γ>0γ>0 and integers Δ≥2Δ≥2 and k≥1k≥1, we prove that there exist constants β>0β>0 and C>0C>0 such that for all p≥C(logn/n)1/Δp≥C(logn/n)1/Δ the random graph G(n,p)G(n,p) asymptotically almost surely contains – even after an adversary deletes an arbitrary (1/k−γ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 Cmax{p−2,p−1logn}Cmax{p−2,p−1logn} vertices not in triangles.
| Item Type | Conference or Workshop Item (Paper) |
|---|---|
| Keywords | extremal graph theory,random graphs,sparse regularity,resilience |
| Departments | Mathematics |
| Date Deposited | 09 Dec 2015 11:38 |
| URI | https://researchonline.lse.ac.uk/id/eprint/64637 |
ORCID: https://orcid.org/0000-0001-6555-3501
ORCID: https://orcid.org/0000-0002-4104-3635