1207.1927 (Charles D. Brummitt et al.)

Jigsaw percolation: Can a random graph solve a puzzle?    [PDF]

Charles D. Brummitt, Shirshendu Chatterjee, Partha S. Dey, David Sivakoff

We introduce a new kind of percolation on finite graphs called jigsaw percolation. This model attempts to capture networks of people who innovate by merging ideas and who collaboratively solve problems by piecing together solutions. Each node of a graph (regarded as a person in a social network) has a unique piece of a jigsaw puzzle. Acquainted people with compatible puzzle pieces merge their puzzle pieces. More generally, groups of people with merged puzzle pieces merge if the groups know one another and have a pair of compatible puzzle pieces. The social network solves the puzzle if it eventually merges all the puzzle pieces. For the case of an Erd\H{o}s-R\'{e}nyi social network with $n$ vertices and edge probability $p_n$, we define the critical value $p_c(n)$ for an arbitrary connected puzzle graph to be the value of $p_n$ for which the probability of solving the puzzle equals 1/2. We prove that when the puzzle graph is the $n$-cycle, then $p_c(n) = \Theta(1/\log n)$. For an arbitrary connected puzzle graph with bounded maximum degree (as $n \to \infty$), we prove that $p_c(n) = O(1/\log n)$ and $p_c(n) = \omega(1/n^b)$ for any $b>0$. These results provide a mechanism for the recent statistical claims that the more people interact, the more they innovate.

View original: http://arxiv.org/abs/1207.1927