Local Resilience for Containment of Bounded Degree Spanning Subgraphs
Abstract
We prove that for all Δ≥ 2 and γ> 0, there exists a constant C = C(Δ, γ) such that for p≥ C(log n/n)1/Δ, asymptotically almost surely, every spanning subgraph G of G(n,p) with minimum degree at least (1−1/(2Δ)+γ)pn contains every n-vertex graph H with maximum degree at most Δ and with at least Cp−2 vertices not in any triangles of H. This is a 'sparse local resilience version' of a classical theorem of Sauer and Spencer. The condition that H should contain some vertices not in triangles is necessary, and in fact, the quantity p−2 is asymptotically best possible. A key feature of our result is that H is allowed to be an expander graph, distinguishing it from previous results of similar nature, which dealt with, e.g., graphs of sublinear bandwidth. Our proof makes use of regularity arguments, with the sparse blow-up lemma for random graphs being a key tool.
Related
BibTeX
@misc{allen2026local,
title = {{Local Resilience for Containment of Bounded Degree Spanning Subgraphs}},
author = {Peter Allen and Julia Böttcher and Yoshiharu Kohayakawa and Mihir Neve},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14834},
eprint = {2609.14834},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14834},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Local Resilience for Containment of Bounded Degree Spanning Subgraphs
AU - Peter Allen
AU - Julia Böttcher
AU - Yoshiharu Kohayakawa
AU - Mihir Neve
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2609.14834
UR - https://arxiv.org/abs/2609.14834
AB - We prove that for all Δ≥ 2 and γ> 0, there exists a constant C = C(Δ, γ) such that for p≥ C(log n/n)^1/Δ, asymptotically almost surely, every spanning subgraph G of G(n,p) with minimum degree at least (1−1/(2Δ)+γ)pn contains every n-vertex graph H with maximum degree at most Δ and with at least Cp^−2 vertices not in any triangles of H. This is a 'sparse local resilience version' of a classical theorem of Sauer and Spencer. The condition that H should contain some vertices not in triangles is necessary, and in fact, the quantity p^−2 is asymptotically best possible. A key feature of our result is that H is allowed to be an expander graph, distinguishing it from previous results of similar nature, which dealt with, e.g., graphs of sublinear bandwidth. Our proof makes use of regularity arguments, with the sparse blow-up lemma for random graphs being a key tool.
ER -