The threshold for jigsaw percolation on random graphs

MaRDI QIDQ2363097zbMATH OpenFDO

Authors Béla Bollobás, Erik Slivken, Paul Smith, Oliver Riordan

Publication date 13 July 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05186, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p36

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

jigsaw percolationrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: Jigsaw percolation is a model for the process of solving puzzles within a social network, which was recently proposed by Brummitt, Chatterjee, Dey and Sivakoff. In the model there are two graphs on a single vertex set (the `people' graph and the `puzzle' graph), and vertices merge to form components if they are joined by an edge of each graph. These components then merge to form larger components if again there is an edge of each graph joining them, and so on. Percolation is said to occur if the process terminates with a single component containing every vertex. In this note we determine the threshold for percolation up to a constant factor, in the case where both graphs are ErdH{o}s--R'enyi random graphs.

Review text

Summary: Jigsaw percolation is a model for the process of solving puzzles within a social network, which was recently proposed by \textit{C. D. Brummitt} [Ann. Appl. Probab. 25, No. 4, 2013--2038 (2015; Zbl 1322.60210)]. In the model there are two graphs on a single vertex set (the `people' graph and the `puzzle' graph), and vertices merge to form components if they are joined by an edge of each graph. These components then merge to form larger components if again there is an edge of each graph joining them, and so on. Percolation is said to occur if the process terminates with a single component containing every vertex. In this note we determine the threshold for percolation up to a constant factor, in the case where both graphs are Erdős-Rényi random graphs.

Recommendations

• The sharp threshold for jigsaw percolation in random graphs
• Jigsaw percolation on random hypergraphs
• Multi-coloured jigsaw percolation on random graphs
• Continuity of the percolation threshold in randomly grown graphs.
• On percolation in random graphs with given vertex degrees
• The sharp threshold for percolation on expander graphs
• scientific article; zbMATH DE number 5722221
• Percolation on random graphs with a fixed degree sequence
• On the range of bond percolation thresholds for fully triangulated graphs
• Critical percolation on certain nonunimodular graphs

Cites work

• Finite size scaling in three-dimensional bootstrap percolation
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Metastability effects in bootstrap percolation
• Nucleation scaling in jigsaw percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation

Cited in

(10)

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

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

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