The time of bootstrap percolation with dense initial sets for all thresholds1. Issue 1 (7th April 2014) - Bollobas, Béla; Smith, Paul; Uzzell, Andrew J.
ABSTRACT We study the percolation time of the r‐neighbour bootstrap percolation model on the discrete torus <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqhph9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(ℤ/nℤ)d</alternatives>. For t at most a polylog function of n and initial infection probabilities within certain ranges depending on t, we prove that the percolation time of a random subset of the torus is exactly equal to t with high probability as n tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understanding of the geometric behaviour of the r‐neighbour bootstrap process in the dense setting. The special case <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqhp6b" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />d−r=0</alternatives> of our result was proved recently by Bollobas, Holmgren, Smith and Uzzell. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 1–29, 2015