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

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.