Loading Events

« All Events

  • This event has passed.
:

Tuan Anh Do, Rank- and tree-width of supercritical random graphs

March 14 Monday @ 4:30 PM - 5:30 PM KST

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

Speaker

Tuan Anh Do (Tuấn Anh Đỗ)
Graz University of Technology / IBS Discrete Mathematics Group

It is known that the rank- and tree-width of the random graph $G(n,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$, the rank- and tree-width are bounded above by a constant, for supercritical $p$, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of Benjamini, Kozma, and Wormald on the expansion of supercritical random graphs. We give a new, short, and direct proof of these results, leading to more explicit bounds on these parameters, and also consider the rank- and tree-width of supercritical random graphs closer to the critical point, showing that this phase transition is smooth.

This is joint work with Joshua Erde and Mihyun Kang.

Details

Date:
March 14 Monday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

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

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.