RANDOM DISEASE ON THE SQUARE GRID

We introduce some generalizations of a nice combinatorial problem, the central notion of which is the so-called Disease Process. Let us colo r independently each square of an nxn chessboard black with a probabil ity p(n); this is a random initial configuration of our process. Then we have a deterministic painting or expansion rule, and the question i s the behavior of the disease process determined by this rule of sprea ding. In particular, how large must p(n) be to paint the whole chessbo ard black? The main result of this paper is the almost exact determina tion of the threshold function in the fundamental case of this Random Disease Problem. We include further investigations into the general ra ndomized and deterministic cases. (C) 1998 John Wiley & Sons, Inc.