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 soon. 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 Erdos-Renyi random graphs. |
Year | Venue | Field |
---|---|---|
2017 | ELECTRONIC JOURNAL OF COMBINATORICS | Random regular graph,Discrete mathematics,Block graph,Combinatorics,Indifference graph,Line graph,Vertex (graph theory),Symmetric graph,1-planar graph,Continuum percolation theory,Mathematics |
DocType | Volume | Issue |
Journal | 24 | 2 |
ISSN | Citations | PageRank |
1077-8926 | 1 | 0.43 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bela Bollobas | 1 | 66 | 12.05 |
Oliver Riordan | 2 | 285 | 38.31 |
erik slivken | 3 | 3 | 0.83 |
Paul Smith | 4 | 3 | 1.60 |