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).
본 논문에서는 무작위 그래프 G(n,p)의 rank와 rank-width의 점근적 분포에 대해 연구하였다. 무작위 그래프 G(n,p)는 n개의 점 위에서 점 두 개 마다 변이 p의 확률로 존재하는 확률적 그래프이다. 그리고 그래프의 rank란 그 그래프의 인접 행렬의 rank를 말한다.
첫 번째로 유한 체 $F_2$ 위에서 G(n,1/2)의 rank의 확률분포를 계산하였다. 먼저 G(2n,1/2)이 역행렬을 가질 확률이 0.4194..로 수렴함을 보였으며, 일반적으로 유한 체 위에서 균등한 확률 분포를 가지는 무작위 skew-symmetric 행렬이 역행렬을 가질 확률을 계산하였다. 그 과정에서 그간 알려졌던 Carlitz의 대수적인 방법 대신 마코프 연쇄를 사용하는 확률적인 방법을 새로 개발하였고, 따라서 그간 알려지지 않은 일반화가 가능했다.
두 번째로 G(n,p)의 rank-width의 점근적인 분포에 대해 연구하였다. rank-width는 엄상일-Seymour가 2006년 정의한 그래프 파라미터로, 이에 관해 다음의 사실들을 보였다.
(i) 만약 p$\in$(0,1) 가 상수이면, $\mathbf{rw}(G(n,p)) = \lceil \frac{n}{3}\rceil-O(1)$,
(ii)$\frac{1}{n}\ll p \leq \frac{1}{2}$ 이면, $\mathbf{rw}(G(n,p)) = \lceil \frac{n}{3}\rceil-o(n)$,
(iii) $p = \frac{c}{n}$ 이고 $c > 1$ 이면, 어떤 상수 $r=r(c)$에 대해 $\mathbf{rw}(G(n,p)) \geq r n$,
(iv) $p \leq \frac{c}{n}$ 이고 $c<1$ 이면, $\mathbf{rw}(G(n,p)) \le 2$ 이 성립한다.
따라서, G(n,p)가 $p(n)=\frac{1}{n}$을 경계로 이보다 작으면 상수 크기, 크면 선형 크기의 tree-width를 가지게 됨도 보였으며, 이것은 Gao가 2006년 제안한 미해결 문제에 대한 답이다.
