Bootstrap percolation on products of cycles and complete graphs

Janko Gravner, David Sivakoff

Published 2015-05-13Version 1

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 every 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$.