  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 solve problems by piecing together solutions. Each 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 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 a connected puzzle graph to be the $p_n$ for which
the chance of solving the puzzle equals $1/2$. We prove that for the $n$-cycle
(ring) puzzle, $p_c(n)=\Theta(1/\log n)$, and for an arbitrary connected puzzle
graph with bounded maximum degree, $p_c(n)=O(1/\log n)$ and $\omega(1/n^b)$ for
any $b>0$. Surprisingly, with probability tending to 1 as the network size
increases to infinity, social networks with a power-law degree distribution
cannot solve any bounded-degree puzzle. This model suggests a mechanism for
recent empirical claims that innovation increases with social density, and it
might begin to show what social networks stifle creativity and what networks
collectively innovate.
