Bootstrap percolation on a graph iteratively enlarges a set of occupied sites by adjoining points with at least $theta$ occupied neighbors. The initially occupied set is random, given by a uniform product measure, and we say that spanning occurs if e
very point eventually becomes occupied. The main question concerns the critical probability, that is, the minimal initial density that makes spanning likely. The graphs we consider are products of cycles of $m$ points and complete graphs of $n$ points. The major part of the paper focuses on the case when two factors are complete graphs and one factor is a cycle. We identify the asymptotic behavior of the critical probability and show that, when $theta$ is odd, there are two qualitatively distinct phases: the transition from low to high probability of spanning as the initial density increases is sharp or gradual, depending on the size of $m$.
Jigsaw percolation is a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of a random people graph on the same set of vertices. We presume the Erdos--Renyi people graph with e
dge probability p and investigate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. In some generality, for puzzle graphs with N vertices of degrees about D (in the appropriate sense), this probability is close to 1 or small depending on whether pD(log N) is large or small. The one dimensional ring and two dimensional torus puzzles are studied in more detail and in many cases the exact scaling of the critical probability is obtained. The paper settles several conjectures posed by Brummitt, Chatterjee, Dey, and Sivakoff who introduced this model.
