The threshold for jigsaw percolation on random graphs

zbMATH Open1366.05096arXiv1503.05186MaRDI QIDQ2363097FDOQ2363097

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)

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.

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

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

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

zbMATH Keywords

random graphsjigsaw percolation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• 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
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles
• Bootstrap percolation on the stochastic block model
• Transitive closure in a polluted environment
• Jigsaw percolation on random hypergraphs
• 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)