The threshold for jigsaw percolation on random graphs
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...
| Автори: | , , , |
|---|---|
| Формат: | Journal article |
| Опубліковано: |
Electronic Journal of Combinatorics
2017
|
| _version_ | 1826289232051699712 |
|---|---|
| author | Bollobás, B Riordan, O Slivken, E Smith, P |
| author_facet | Bollobás, B Riordan, O Slivken, E Smith, P |
| author_sort | Bollobás, B |
| collection | OXFORD |
| description | 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˝os–R´enyi random graphs. |
| first_indexed | 2024-03-07T02:25:45Z |
| format | Journal article |
| id | oxford-uuid:a587b64f-8e3f-4806-904d-6ca844903436 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:25:45Z |
| publishDate | 2017 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | oxford-uuid:a587b64f-8e3f-4806-904d-6ca8449034362022-03-27T02:41:07ZThe threshold for jigsaw percolation on random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:a587b64f-8e3f-4806-904d-6ca844903436Symplectic Elements at OxfordElectronic Journal of Combinatorics2017Bollobás, BRiordan, OSlivken, ESmith, PJigsaw 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˝os–R´enyi random graphs. |
| spellingShingle | Bollobás, B Riordan, O Slivken, E Smith, P The threshold for jigsaw percolation on random graphs |
| title | The threshold for jigsaw percolation on random graphs |
| title_full | The threshold for jigsaw percolation on random graphs |
| title_fullStr | The threshold for jigsaw percolation on random graphs |
| title_full_unstemmed | The threshold for jigsaw percolation on random graphs |
| title_short | The threshold for jigsaw percolation on random graphs |
| title_sort | threshold for jigsaw percolation on random graphs |
| work_keys_str_mv | AT bollobasb thethresholdforjigsawpercolationonrandomgraphs AT riordano thethresholdforjigsawpercolationonrandomgraphs AT slivkene thethresholdforjigsawpercolationonrandomgraphs AT smithp thethresholdforjigsawpercolationonrandomgraphs AT bollobasb thresholdforjigsawpercolationonrandomgraphs AT riordano thresholdforjigsawpercolationonrandomgraphs AT slivkene thresholdforjigsawpercolationonrandomgraphs AT smithp thresholdforjigsawpercolationonrandomgraphs |