Twin-width of random graphs
share
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^*≈ 0.4 such that with high probability, when p^*≤ p≤ 1-p^*, the twin-width is asymptotically 2p(1-p)n, whereas, when p<p^* or p>1-p^*, the twin-width is significantly higher than 2p(1-p)n. In particular, we show that the twin-width of G(n,1/2) is concentrated around n/2 - (√(3n log n))/2 within an interval of length o(√(nlog n)). For the sparse random graph, we show that with high probability, the twin-width of G(n,p) is Θ(n√(p)) when (726ln n)/n≤ p≤1/2.
READ FULL TEXT