Jigsaw Percolation on Erdos-Renyi Random Graphs

Abstract

We extend the jigsaw percolation model to analyze graphs where both underlying people and puzzle graphs are Erdős-Rényi random graphs. Let $p_{\text{ppl}}$ and $p_{\text{puz}}$ denote the probability that an edge exists in the respective people and puzzle graphs and define $p_{\text{eff}}=p_{\text{ppl}}{p}_{\text{puz}}$, the effective probability. We show for constants $c_1>1$ and $c_2>{\pi }^2/6$ and $c_3<e^{-5}$ if $min(p_{\text{ppl}},p_{\text{puz}})>c_1\log n/n$ the critical effective probability $p_{\text{eff}}^c$, satisfies $c_3<p_{\text{eff}}^{c}n\log n<c_2.$

Merged with arXiv:1503.05186