기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2017 Discrete Math 세미나
Title Spanning trees in a randomly perturbed graphs
Speaker Jaehoon Kim  (  Birmingham University, UK  ) Date 2017-12-28
Host KAIST Place KAIST
VOD    
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.

이 페이지에서 제공하는 정보에 만족하십니까?