A generating function approach to random subgraphs of the n-cycle
Abstract.
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.
helmut@gauss.cam.wits.ac.za
Xavier.Gourdon@inria.fr
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)