On threshold properties

Abstract

In this paper we consider two random graph models and their relationship. More specifically, we consider the random graph model G_n,m , where a random graph is constructed by drawing uniformly and independently m edges out of the possible edges without repetition, and the random graph model G_n,mm where a random graph is constructed by the same process, but the an edge is allowed to be selected more than once. We prove that the property of a random graph G of the latter model having multiple edges is a threshold property, with threshold function t(n) = n. Moreover, if m = cn for some positive real number c, then the probability that a random graph G has multiple edges approaches exp(–c ²).