Twin-width of random graphs

Abstract

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^{\ast }\approx 0.4$ such that with high probability, when $p^{\ast }\le p\le 1-p^{\ast }$, the twin-width is asymptotically $2p(1-p)n$, whereas, when $0<p<p^{\ast }$ or $1>p>1-p^{\ast }$, 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 $\Theta (n\sqrt{p})$ when $(726\ln n)/n\le p\le 1/2$.

37 pages, 3 figures

References in corpus (1)

• Bounds for the Twin-width of Graphs

Cited by in corpus (3)

• Twin-width of subdivisions of multigraphs
• Twin-width of sparse random graphs
• On the twin-width of near-regular graphs