Journal of Combinatorics

Volume 11 (2020)

Number 4

Multi-coloured jigsaw percolation on random graphs

Pages: 603 – 624

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n4.a2

Authors

Oliver Cooley (Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria)

Abraham Gutierrez (Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria)

Abstract

The jigsaw percolation process, introduced by Brummitt, Chatterjee, Dey and Sivakoff, was inspired by a group of people collectively solving a puzzle. It can also be seen as a measure of whether two graphs on a common vertex set are “jointly connected”. In this paper we consider the natural generalisation of this process to an arbitrary number of graphs on the same vertex set. We prove that if these graphs are random, then the jigsaw percolation process exhibits a phase transition in terms of the product of the edge probabilities. This generalises a result of Bollobás, Riordan, Slivken and Smith.

Keywords

phase transition, random graphs, percolation

2010 Mathematics Subject Classification

05C80

Received 30 November 2017

Accepted 13 August 2019

Published 9 October 2020