Publisher DOI: 10.1016/j.endm.2015.06.071
Title: Local resilience of spanning subgraphs in sparse random graphs
Language: English
Authors: Allen, Peter 
Böttcher, Julia 
Ehrenmüller, Julia 
Taraz, Anusch 
Keywords: Extremal graph theory; Random graphs; Resilience; Sparse regularity
Issue Date: 12-Nov-2015
Publisher: Elsevier Science
Source: Electronic Notes in Discrete Mathematics 49: 513-521 (2015-11)
Abstract (english): 
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.
ISSN: 1571-0653
Journal: Electronic notes in discrete mathematics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.