Skip to main content

Janko Gravner

Title: Jigsaw percolation: a nucleation analysis

Abstract: Jigsaw percolation is a model for collaborative problem solving: a nonlocal process that iteratively merges connected clusters in a deterministic puzzle graph by using connectivity properties of arandom people graph on the same set of vertices. We presume the people graph is random while the puzzle graph is a fixed deterministic graph. The main question is to estimate the probability that the puzzle is solved, that is, that the process eventually produces a single cluster. Particularly sharp answers can be obtained for the one dimensional ring and two dimensional torus puzzles where bootstrap percolation techniques can be used. The talk is on joint work with David Sivakoff.