Multi-coloured jigsaw percolation on random graphs

DOI10.4310/JOC.2020.V11.N4.A2MaRDI QIDQ2223490zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Abraham Gutierrez

Publication date 29 January 2021

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.00992

zbMATH Keywords

percolationphase transitionrandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

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'as, Riordan, Slivken and Smith.

Recommendations

• Jigsaw percolation on random hypergraphs
• The threshold for jigsaw percolation on random graphs
• The sharp threshold for jigsaw percolation in random graphs
• Nucleation scaling in jigsaw percolation
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?

Cited in

(7)

• The size of the giant joint component in a binomial random double graph
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• The threshold for jigsaw percolation on random graphs
• Jigsaw percolation on random hypergraphs
• The sharp threshold for jigsaw percolation in random graphs
• Nucleation scaling in jigsaw percolation
• Unique reconstruction threshold for random jigsaw puzzles

This page was built for publication: Multi-coloured jigsaw percolation on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223490)