Jigsaw Percolation on Erdos-Renyi Random Graphs
Skip to main content
eScholarship
Open Access Publications from the University of California

Jigsaw Percolation on Erdos-Renyi Random Graphs

  • Author(s): Slivken, Erik
  • et al.

Published Web Location

https://arxiv.org/pdf/1503.06346.pdf
No data is associated with this publication.
Abstract

We extend the jigsaw percolation model to analyze graphs where both underlying people and puzzle graphs are Erd\H{o}s-R enyi 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 c_1 \log n /n$ the critical effective probability $p^c_{\text{eff}}$, satisfies $c_3 < p^c_{\text{eff}}n\log n < c_2.$

Item not freely available? Link broken?
Report a problem accessing this item