Acyclicity in Random Graphs

Phil Pollett

Abstract: A random graph with n vertices is constructed in the following way: pairs of vertices are randomly selected one at a time in such a way that each pair has the same probability of being selected on any given occasion, and, each selection is made independently of previous selections. If the vertex pair is selected, then an edge is constructed which connects x and y; multiple edges are allowed.

Suppose that m edges have been selected. We shall consider the behaviour of the graph in the limit as n and m become large, but in such a way that n=cm, where c is a positive constant. In particular, we shall determine the limiting probability that the graph is acyclic.

Acknowledgement: This worked was funded by the Australian Research Council.

The author:

• Phil Pollett, Department of Mathematics, The University of Queensland. pkp@maths.uq.edu.au

Last modified: 9th November 1995