Geodesic
The threshold for jigsaw percolation on random graphs
Béla Bollobás1 ; Oliver Riordan2 ; Erik Slivken3 ; Paul Smith4
1University of Cambridge and University of Memphis
2University of Oxford
3UC Davis
4Tel Aviv University
The electronic journal of combinatorics, Tome 24 (2017) no. 2

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv
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 Erdős-Rényi random graphs.
DOI : 10.37236/6102
Classification : 05C80, 60C05
Mots-clés : jigsaw percolation, random graphs

Béla Bollobás  1   ; Oliver Riordan  2   ; Erik Slivken  3   ; Paul Smith  4

1 University of Cambridge and University of Memphis
2 University of Oxford
3 UC Davis
4 Tel Aviv University 
Béla Bollobás; Oliver Riordan; Erik Slivken; Paul Smith. The threshold for jigsaw percolation on random graphs. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6102
@article{10_37236_6102,
     author = {B\'ela Bollob\'as and Oliver Riordan and Erik Slivken and Paul Smith},
     title = {The threshold for jigsaw percolation on random graphs},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {2},
     doi = {10.37236/6102},
     zbl = {1366.05096},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6102/}
}
TY  - JOUR
AU  - Béla Bollobás
AU  - Oliver Riordan
AU  - Erik Slivken
AU  - Paul Smith
TI  - The threshold for jigsaw percolation on random graphs
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6102/
DO  - 10.37236/6102
ID  - 10_37236_6102
ER  - 
%0 Journal Article
%A Béla Bollobás
%A Oliver Riordan
%A Erik Slivken
%A Paul Smith
%T The threshold for jigsaw percolation on random graphs
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6102/
%R 10.37236/6102
%F 10_37236_6102

Cité par Sources :