TuanAnhDo

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 …