











Title 


Speaker 
Jaehoon Kim 


Date 
20171228 


Host 



Place 
KAIST 




Abstract : A classical result of Komlós, Sárközy and Szemerédi states that every nvertex graph with minimum degree at least (1/2 +o(1))n contains every nvertex 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 nvertex graph G with minimum degree at least αn for any fixed α>0 and every nvertex tree T with bounded maximum degree, one can still find a copy of T in G with high probability after adding O(n) randomlychosen 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 nvertex 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. 





