A classical result of Komlos, Sarkozy, and Szemeredi states that every n-vertex graph with minimum degree at least (1/2 + o(1))n contains every n-vertex tree with maximum degree O(n/logn). Krivelevich, Kwan, and Sudakov proved that for every n-vertex graph G(alpha) with minimum degree at least alpha n for any fixed alpha > 0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in G(alpha) with high probability after adding O(n) randomly chosen edges to G(alpha). We extend the latter results to trees with (essentially) unbounded maximum degree; for a given no(1)<=Delta <= cn/logn and alpha > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n-vertex graph with minimum degree alpha n in order to guarantee with high probability a copy of any fixed n-vertex tree with maximum degree at most Delta.

- Publisher
- WILEY

- Issue Date
- 2020-01

- Language
- English

- Article Type
- Article

- Citation
RANDOM STRUCTURES & ALGORITHMS, v.56, no.1, pp.169 - 219

- ISSN
- 1042-9832

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item
- There are no files associated with this item.

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