Rank and rank-width of random graphs

Abstract

We investigate the asymptotic behaviour of rank and rank-width of a random graph G(n,p). A random graph G(n,p) is a graph on n vertices so that each pair of vertices are adjacent with the probability p independently at random. We study about the rank of a random graph G(n,1/2). The rank of a graph is the rank of an adjacency matrix of a graph over the binary field. We prove that the probability that the adjacency matrix of G(n,1/2) is non-singular converges to 0.4914. More generally we present a new method to calculate the asymptotic distribution of the rank of the skew-symmetric 2n X 2n matrices whose entries are uniformly and randomly chosen from a finite field $F_q$. Unlike previous proofs by Carlitz (1954), we use Markov chains and its stationary distributions, which admits a further generalization. Rank-width is a width parameter of graphs introduced by Oum and Seymour (2006). We show that, asymptotically almost surely. (i) if p$\in$(0,1) is a constant, then rw(G(n,p)) = $\lceil \frac{n}{3}\rceil-O(1)$, (ii) if $\frac{1}{n}\ll p \leq \frac{1}{2}$, then $\mathbf{rw}(G(n,p)) = \lceil \frac{n}{3}\rceil-o(n)$, (iii) if $p = \frac{c}{n}$ and $c > 1$, then $\mathbf{rw}(G(n,p)) \geq r n$ for some $r = r(c)$, and (iv) if $p \leq \frac{c}{n}$ and $c<1$, then $\mathbf{rw}(G(n,p)) \le 2$. As a corollary, we deduce that G(n,p) has linear tree-width whenever $p=\frac{c}{n}$ for each c $\gt$1, answering an open question of Gao (2006).