Twin-width of random graphs

Abstract: We investigate the twin-width of the ErdH{o}s-R'enyi random graph

G (n, p)

. We unveil a surprising behavior of this parameter by showing the existence of a constant

p^{*} a p p r o x 0.4

such that with high probability, when

p^{*} l e p l e 1 - p^{*}

, the twin-width is asymptotically

2 p (1 - p) n

, whereas, when

p < p^{*}

or

p > 1 - p^{*}

, the twin-width is significantly higher than

2 p (1 - p) n

. In particular, we show that the twin-width of

G (n, 1 / 2)

is concentrated around

n / 2 - (s q r t 3 n l o g n) / 2

within an interval of length

o (s q r t n l o g n)

. For the sparse random graph, we show that with high probability, the twin-width of

G (n, p)

is

T h e t a (n s q r t p)

when

(726 l n n) / n l e q p l e q 1 / 2

.

This page was built for publication: Twin-width of random graphs