Twin-width of random graphs

MaRDI QIDQ6507323arXivFDO

Authors Jung-Ho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, Sang-Il Oum

Published in arXiv

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

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^{\ast }approx0.4$ such that with high probability, when $p^{\ast }leple1-p^{\ast }$, the twin-width is asymptotically $2p(1-p)n$, whereas, when $p<p^{\ast }$ or $p>1-p^{\ast }$, 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-(sqrt3nlogn)/2$ within an interval of length $o(sqrtnlogn)$. For the sparse random graph, we show that with high probability, the twin-width of $G(n,p)$ is $Theta(nsqrtp)$ when $(726lnn)/nleqpleq1/2$.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507323)