Loading Events

« All Events

  • This event has passed.
:

Dong Yeap Kang (강동엽), Fragile minor-monotone parameters under random edge perturbation

February 18 Tuesday @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Dong Yeap Kang (강동엽)
KAIST / IBS Discrete Mathematics Group
http://mathsci.kaist.ac.kr/~dykang/

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases. We also discuss analogous results for randomly perturbed bipartite graphs as well as the size of a largest complete odd minor in randomly perturbed graphs.

Details

Date:
February 18 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/