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

random graphsjigsaw percolation

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.

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)

• 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
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Bootstrap percolation on the stochastic block model
• Jigsaw percolation on random hypergraphs
• Transitive closure in a polluted environment
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• The sharp threshold for jigsaw percolation in random graphs
• Nucleation scaling in jigsaw percolation

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)