Zero-one laws for sparse random graphs

Abstract

For random graph theorists (see, e.g., Bollobas [1] for general reference) p any constant is not the only, not even the most interesting case. Rather, they consider p = p(n), a function approaching zero. In their seminal paper, Erd6s and Renyi [5] showed that for many interesting A there is a function p(n), which they called a threshold function, so that if r(n) < p(n) then f(n, r(n), A) -+ 0 while if p(n) < r(n) then f(n, r(n), A) 1-+ . (Notation: p < r means lim p/r = 0. All limits are as n approaches infinity.) Let us say p = p(n) satisfies the Zero-One Law if for all A in GRA, limf(n, p, A) = 0 or 1. We shall partially characterize those p = p(n) which satisfy the Zero-One Law.

Locations

• Journal of the American Mathematical Society - View - PDF