Ballots, queues and random graphs

This paper demonstrates how a simple ballot theorem leads, through the interjection of a queueing process, to the solution of a problem in the theory of random graphs connected with a study of polymers in chemistry. Let ¦)n(p) denote a random graph with n vertices in which any two vertices, independently of the others, are connected by an edge with probability p where 0<p<1. Denote by ρn(s) the number of vertices in the union of all those components of ¦)n(p) which contain at least one vertex of a given set of s vertices. This paper is concerned with the determination of the distribution of ρn(s) and the limit distribution of ρn(s) as n⇒• and p⇒0 in such a way that np⇒a where a is a positive real number.