A note on the width of sparse random graphs

TA Do, J Erde, M Kang - Journal of Graph Theory, 2024 - Wiley Online Library
TA Do, J Erde, M Kang
Journal of Graph Theory, 2024Wiley Online Library
In this note, we consider the width of a supercritical random graph according to some
commonly studied width measures. We give short, direct proofs of results of Lee, Lee and
Oum, and of Perarnau and Serra, on the rank‐and tree‐width of the random graph G (n, p)
G(n,p) when p= 1+ ϵ np=1+ϵn for ϵ> 0 ϵ\gt0 constant. Our proofs avoid the use of black
box results on the expansion properties of the giant component in this regime, and so as a
further benefit we obtain explicit bounds on the dependence of these results on ϵ ϵ. Finally …
Abstract
In this note, we consider the width of a supercritical random graph according to some commonly studied width measures. We give short, direct proofs of results of Lee, Lee and Oum, and of Perarnau and Serra, on the rank‐ and tree‐width of the random graph G(n,p) $G(n,p)$ when p=1+ϵn $p=\frac{1+\epsilon }{n}$ for ϵ>0 $\epsilon \gt 0$ constant. Our proofs avoid the use of black box results on the expansion properties of the giant component in this regime, and so as a further benefit we obtain explicit bounds on the dependence of these results on ϵ $\epsilon $. Finally, we also consider the width of the random graph in the weakly supercritical regime, where ϵ=o(1) $\epsilon =o(1)$ and ϵ3n→∞ ${\epsilon }^{3}n\to \infty $. In this regime, we determine, up to a constant multiplicative factor, the rank‐ and tree‐width of G(n,p) $G(n,p)$ as a function of n $n$ and ϵ $\epsilon $.
Wiley Online Library
以上显示的是最相近的搜索结果。 查看全部搜索结果