The threshold for jigsaw percolation on random graphs

Bollobás, Béla; Riordan, Oliver; Smith, Paul
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. Improving on a result of Slivken, in this note we determine the threshold for percolation up to a constant factor, in the case where both graphs are Erd$\backslash$H{\{}o{\}}s--R$\backslash$'enyi random graphs.
Research areas:
Type of Publication:
317532; and multiplex grant no; and phrases; b; is partially supported by; jigsaw percolation; nsf grant dms 1301614; random graphs
Hits: 3477

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information