DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Oum, Sang-il | - |
dc.contributor.advisor | 엄상일 | - |
dc.contributor.author | Lee, Joon-Kyung | - |
dc.contributor.author | 이준경 | - |
dc.date.accessioned | 2011-12-14T04:56:55Z | - |
dc.date.available | 2011-12-14T04:56:55Z | - |
dc.date.issued | 2010 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=419038&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/42229 | - |
dc.description | 학위논문(석사) - 한국과학기술원 : 수리과학과, 2010.2, [ iii, 20 p. ] | - |
dc.description.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). | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | rank-width | - |
dc.subject | rank of a graph | - |
dc.subject | random graph | - |
dc.subject | random matrix | - |
dc.subject | 무작위 행렬 | - |
dc.subject | rank-width | - |
dc.subject | 그래프의 rank | - |
dc.subject | 무작위 그래프 | - |
dc.title | Rank and rank-width of random graphs | - |
dc.title.alternative | 무작위 그래프의 rank와 rank-width | - |
dc.type | Thesis(Master) | - |
dc.identifier.CNRN | 419038/325007 | - |
dc.description.department | 한국과학기술원 : 수리과학과, | - |
dc.identifier.uid | 020083414 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.localauthor | 엄상일 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.