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.
|
