@article{9590,
abstract = {We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is c=c(α,Δ) such that if G is an n-vertex graph with minimum degree at least αn, and T is an n-vertex tree with maximum degree at most Δ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as n→∞ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest.},
author = {Krivelevich, Michael and Kwan, Matthew Alan and Sudakov, Benny},
issn = {1095-7146},
journal = {SIAM Journal on Discrete Mathematics},
number = {1},
pages = {155--171},
publisher = {Society for Industrial & Applied Mathematics},
title = {{Bounded-degree spanning trees in randomly perturbed graphs}},
doi = {10.1137/15m1032910},
volume = {31},
year = {2017},
}