Random subgraphs of the n-cycle (Q800378): Difference between revisions

Let \(C_ n\) denote the undirected n-cycle with vertices \(v_ 1,...,v_ n\) and edges \(\{v_ 1,v_ 2\}\), \(\{v_ 2,v_ 3),...,\{v_ n,v_ 1\}\). Let \(RC_ n(p)\) (0\(\leq p\leq 1)\) denote the random subgraph of \(C_ n\), having the same vertices as \(C_ n\) and being such that each edge of \(C_ n\) is selected or rejected with probability p or 1-p, respectively (different edges being treated independently). The authors investigate e.g. the asymptotic behaviour (as \(n\to\infty \)) of \(X_ 0(n)\) (the number of isolated vertices of \(RC_ n(p))\) and M(n) (the number of isolated vertices of \(RC_ n(p))\) and M(n) (the order of the largest connected component of \(RC_ n(p))\). It is shown, e.g., that if \(p=1-w(n)/\sqrt{n}\), \((x_ 0(n)-w^ 2(n)/w(n)\) asymptotically has a standard normal distribution.