Spanning trees in a randomly perturbed graphs

2017/12/28 **Thursday 2PM-3PM** (Room 3433)

A classical result of Komlós, Sárközy and Szemerédi states that every n-vertex graph with minimum degree at least (1/2 +o(1))n contains every n-vertex tree with maximum degree at most O(n/log n) as a subgraph, and the bounds on the degree conditions are sharp.

On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every n-vertex graph G with minimum degree at least αn for any fixed α>0 and every n-vertex tree T with bounded maximum degree, one can still find a copy of T in G with high probability after adding O(n) randomly-chosen edges to G.

We extend this result to trees with unbounded maximum degree. More precisely, for a given n^{ε} ≤ Δ≤ cn/log n and α>0, we determined the precise number (up to a constant factor) of random edges that we need to add to an arbitrary n-vertex graph G with minimum degree αn in order to guarantee with high probability a copy of any fixed T with maximum degree at most Δ. This is joint work with Felix Joos.