• 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:

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

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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