Twin-width of random graphs

Abstract

We investigate the twin-width of the Erdos-Renyi random graph G n,p). We unveil a surprising behavior of this parameter by showing the existence of a constant p & lowast;approximate to 0.4such that with high probability, when p & lowast;<= p <= 1-p & lowast;,the twin-width is asymptotically 2p(1-p)n, whereas, when0<p<p & lowast;or 1>p>1-p & lowast;, 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 aroundn/2-root 3nlogn/2 within an interval of length o(root n log n).For the sparse random graph, we show that with high probability, the twin-width of G(n,p) is Theta (n root p) when (726 ln n)/ n <= p <= 1/2