Random disease on the square grid

József Balogh, Gábor Pete

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce some generalizations of a nice combinatorial problem, the central notion of which is the so-called Disease Process. Let us color independently each square of an n × n chessboard black with a probability p(n); this is a random initial configuration of our process. Then we have a deterministic painting or expansion rule, and the question is the behavior of the disease process determined by this rule of spreading. In particular, how large must p(n) be to paint the whole chessboard black? The main result of this paper is the almost exact determination of the threshold function in the fundamental case of this Random Disease Problem. We include further investigations into the general randomized and deterministic cases.

Original languageEnglish (US)
Pages (from-to)409-422
Number of pages14
JournalRandom Structures and Algorithms
Volume13
Issue number3-4
DOIs
StatePublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Random disease on the square grid'. Together they form a unique fingerprint.

Cite this