Twin‐width of random graphs
Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, Donggyu Kim, Sang‐il Oum · Random Structures and Algorithms · 2024
Abstract We investigate the twin‐width of the Erdős‐Rényi random graph . We unveil a surprising behavior of this parameter by showing the existence of a constant such that with high probability, when , the twin‐width is asymptotically , whereas, when or , the twin‐width is significantly higher than . In addition, we show that the twin‐width of is concentrated around within an interval of length . For the sparse random graph, we show that with high probability, the twin‐width of is when .