The sharp threshold for jigsaw percolation in random graphs

Abstract

We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected'. Bollobás, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $\Theta \left(\frac{1}{n\ln n}\right)$. We show that this threshold is sharp, and that it lies at $\frac{1}{4n\ln n}$.

22 pages

References in corpus (3)

• Catastrophic cascade of failures in interdependent networks
• Hyperbolic Geometry of Complex Networks
• Jigsaw percolation: What social networks can collaboratively solve a puzzle?

Cited by in corpus (1)

• Transitive closure in a polluted environment