The sharp threshold for jigsaw percolation in random graphs

DOI10.1017/APR.2019.24zbMATH Open1427.05207arXiv1809.01907OpenAlexW2889807312WikidataQ127402251 ScholiaQ127402251MaRDI QIDQ5203940FDOQ5203940

Authors: Oliver Cooley, Tobias Kapetanopoulos, Tamás Makai 

Publication date: 9 December 2019

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

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

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

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

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)

Cites Work

• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The degree sequence of a scale-free random graph process
• A Remark on Stirling's Formula
• Title not available (Why is that?)
• Nucleation scaling in jigsaw percolation
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• The threshold for jigsaw percolation on random graphs
• Multi-coloured jigsaw percolation on random graphs
• Jigsaw percolation on random hypergraphs

Cited In (8)

• Title not available (Why is that?)
• 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
• Transitive closure in a polluted environment
• Jigsaw percolation on random hypergraphs
• 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)