---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Michael
foaf_name: Krivelevich, Michael
foaf_surname: Krivelevich
- foaf_Person:
foaf_givenName: Matthew Alan
foaf_name: Kwan, Matthew Alan
foaf_surname: Kwan
foaf_workInfoHomepage: http://www.librecat.org/personId=5fca0887-a1db-11eb-95d1-ca9d5e0453b3
- foaf_Person:
foaf_givenName: Benny
foaf_name: Sudakov, Benny
foaf_surname: Sudakov
bibo_doi: 10.1137/15m1032910
bibo_issue: '1'
bibo_volume: 31
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0895-4801
- http://id.crossref.org/issn/1095-7146
dct_language: eng
dct_publisher: Society for Industrial & Applied Mathematics@
dct_title: Bounded-degree spanning trees in randomly perturbed graphs@
...