Rank-width of random graphs

Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymp-totic behavior of rank-width of a random graph G(n, p). We show that, asymp-totically almost surely, (i) if p ∈ (0, 1) is a constant, then rw(G(n, p)) = dn3 e −O(1), (ii) if 1n p ≤ 12, then rw(G(n, p)) = dn3 e − o(n), (iii) if p = c/n and c> 1, then rw(G(n, p)) ≥ rn for some r = r(c), and (iv) if p ≤ c/n and c < 1, then rw(G(n, p)) ≤ 2. As a corollary, we deduce that the tree-width of G(n, p) is linear in n whenever p = c/n for each c> 1, answering a question of Gao (2006)