The sharp threshold for jigsaw percolation in random graphs

DOI10.1017/APR.2019.24MaRDI QIDQ5203940zbMATH OpenOpenAlexWikidataFDO

Authors Oliver Cooley, Tobias Kapetanopoulos, Tamás Makai

Publication date 9 December 2019

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.01907

zbMATH Keywords

phase transitionrandom graphsharp thresholdjigsaw percolation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

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'as, 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 $Thetaleft(frac1nlnnight)$. We show that this threshold is sharp, and that it lies at $frac14nlnn$.

Recommendations

• The threshold for jigsaw percolation on random graphs
• Multi-coloured jigsaw percolation on random graphs
• Jigsaw percolation on random hypergraphs
• Nucleation scaling in jigsaw percolation
• The sharp threshold for percolation on expander graphs

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 1231230 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Remark on Stirling's Formula
• Emergence of Scaling in Random Networks
• Jigsaw percolation on random hypergraphs
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Multi-coloured jigsaw percolation on random graphs
• Nucleation scaling in jigsaw percolation
• The degree sequence of a scale-free random graph process
• The threshold for jigsaw percolation on random graphs

Cited in

(8)

• scientific article; zbMATH DE number 5778129 (Why is no real title available?)
• Multi-coloured jigsaw percolation on random graphs
• The size of the giant joint component in a binomial random double graph
• The threshold for jigsaw percolation on random graphs
• Jigsaw percolation on random hypergraphs
• Transitive closure in a polluted environment
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Nucleation scaling in jigsaw percolation

This page was built for publication: The sharp threshold for jigsaw percolation in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203940)