论文标题
关于稀疏随机图的宽度的注释
A note on the width of sparse random graphs
论文作者
论文摘要
在本说明中，我们根据一些常见的宽度度量考虑了超临界随机图的宽度。我们在$ p = \ frac {1+frac {1+ε} {n} $ for $ε> 0 $常数时，在随机图$ g（n，p）$的等级和树宽度上提供了李，李和欧姆以及perarnau和serra的结果的简短，直接证明。我们的证明避免了本杰米尼，科兹马和蠕虫在该制度中巨型组件的扩展特性结果的黑匣子的用途，因此，作为进一步的好处，我们获得了对这些依赖性的明确界限。最后，我们还考虑了弱超临界方案中随机图的宽度，其中$ε= o（1）$和$ε^3n \ to \ infty $。在此制度中，我们确定$ g（n，p）$的排名和树宽度为$ n $和$ε$。
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)$ when $p= \frac{1+ε}{n}$ for $ε> 0$ constant. Our proofs avoid the use, as a black box, of a result of Benjamini, Kozma and Wormald 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, we also consider the width of the random graph in the weakly supercritical regime, where $ε= o(1)$ and $ε^3n \to \infty$. In this regime, we determine, up to a constant multiplicative factor, the rank- and tree-width of $G(n,p)$ as a function of $n$ and $ε$.
