Coloring percolation clusters at random

We consider the random coloring of the vertices of a graph G, that arises by first performing i.i.d. bond percolation with parameter p on G, and then assigning a random color, chosen according to some prescribed probability distribution on the finite set {0,..., r-1}, to each of the connected components, independently for different components. We call this the divide and color model, and study its percolation and Gibbs (quasilocality) properties, with emphasis on the case G = Z(d). On Z(2), having an infinite cluster in the underlying bond percolation process turns out to be necessary and sufficient for some single color to percolate; this fails in higher k-dimensions. Gibbsianness of the coloring process on Z(d), d greater than or equal to 2, holds when p is sufficiently small, but not when p is sufficiently large. For r = 2, an FKG inequality is also obtained. (C) 2001 Elsevier Science B.V. All rights reserved.