A generating function approach to random subgraphs of the n-cycle

✍ Scribed by Xavier Gourdon; Helmut Prodinger

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 226 KB
• Volume: 169
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00164-r

✦ Synopsis

Given a cycle with n nodes a random subgraph is created by 'accepting' edges with probability p and 'rejecting' them with probability q = 1 -p. The parameter of interest is the order of the largest component. There are some partial answers to this question in the literature. Using an appropriate encoding by formal languages, we present here a complete solution. Singularity analysis of generating functions gives good approximations of the probabilities, and the asymptotic evaluation of expectation and variance is performed by the Mellin (integral) transform. For instance, the expected order is like a logarithm of n plus an oscillating function.