论文标题
随机图的双宽度
Twin-width of random graphs
论文作者
论文摘要
我们研究了Erdős-rényi随机图$ g（n，p）$的双宽度。我们通过显示常数$ p^*\约0.4 $的存在来揭示此参数的令人惊讶的行为，以使概率很高，当$ p^*\ le p \ le p \ le 1-p^*$时，双宽度是偶然的$ 2p（1-p）n $，而当$ 0 <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p <p^*$更高，则是$ 1> p^* $ 2P（1-P）n $。此外，我们表明$ g（n，1/2）$的双宽度集中在$ n/2 - \ sqrt {3n \ log n}/2 $内，间隔为$ o（\ sqrt {n \ log n}）$。对于稀疏的随机图，我们表明，$ g（n，p）$的双宽度为$θ（n \ sqrt {p}）$当$（726 \ ln n）/n \ leq p \ leq p \ leq1/2 $。
We investigate the twin-width of the Erdős-Rényi random graph $G(n,p)$. We unveil a surprising behavior of this parameter by showing the existence of a constant $p^*\approx 0.4$ such that with high probability, when $p^*\le p\le 1-p^*$, the twin-width is asymptotically $2p(1-p)n$, whereas, when $0<p<p^*$ or $1>p>1-p^*$, the twin-width is significantly higher than $2p(1-p)n$. In addition, we show that the twin-width of $G(n,1/2)$ is concentrated around $n/2 - \sqrt{3n \log n}/2$ within an interval of length $o(\sqrt{n\log n})$. For the sparse random graph, we show that with high probability, the twin-width of $G(n,p)$ is $Θ(n\sqrt{p})$ when $(726\ln n)/n\leq p\leq1/2$.
