On the connectedness of a random graph

Abstract

Let p = (p(i): i ≥ 0) be a sequence of numbers satisfying 0 ≤ p(i) < 1 for i = 0,1,2,…, and let G be a random graph with vertex set ℤ = {…, — 1, 0, 1,…} and with edge set defined as follows: for each pair i, j of vertices, where i ≤ j, there is an edge joining i and j with probability p(j — i), independently of the presence or absence of all other edges. We explore the connectedness of G, showing that G is almost surely connected if and only if Σ i p(i) = ∞ and the (positive) greatest common divisor of the set {i ≥ 1: p(i) < 0} equals 1; if one of these two conditions fails to hold then G is almost surely disconnected. Corresponding results hold in higher dimensions, for random graphs defined on the vertex sets ℤ d where d ≥ 2.