Jigsaw percolation on random hypergraphs

DOI10.1017/JPR.2017.62MaRDI QIDQ4684919zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Cooley, Mihyun Kang, Christoph Koch

Publication date 26 September 2018

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random graphbreadth-first searchhypergraphjigsaw percolationhigh-order connectedness

Mathematics Subject Classification ID

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

Abstract: The jigsaw percolation process on graphs was introduced by Brummitt, Chatterjee, Dey, and Sivakoff as a model of collaborative solutions of puzzles in social networks. Percolation in this process may be viewed as the joint connectedness of two graphs on a common vertex set. Our aim is to extend a result of Bollob'as, Riordan, Slivken, and Smith concerning this process to hypergraphs for a variety of possible definitions of connectedness. In particular, we determine the asymptotic order of the critical threshold probability for percolation when both hypergraphs are chosen binomially at random.

Recommendations

• The threshold for jigsaw percolation on random graphs
• Multi-coloured jigsaw percolation on random graphs
• The sharp threshold for jigsaw percolation in random graphs
• Percolation on hyperbolic graphs
• scientific article; zbMATH DE number 5722221
• Percolation on random Johnson-Mehl tessellations and related models
• Percolation in a hierarchical random graph
• On percolation in random graphs with given vertex degrees
• Percolation on random graphs with a fixed degree sequence
• Critical percolation on the kagome hypergraph

Cites work

• Evolution of the social network of scientific collaborations
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Nucleation scaling in jigsaw percolation
• The structure of scientific collaboration networks
• The threshold for jigsaw percolation on random graphs
• Threshold and hitting time for high-order connectedness in random hypergraphs

Cited in

(7)

• Multi-coloured jigsaw percolation on random graphs
• The size of the giant joint component in a binomial random double graph
• The threshold for jigsaw percolation on random graphs
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• The sharp threshold for jigsaw percolation in random graphs
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Nucleation scaling in jigsaw percolation

This page was built for publication: Jigsaw percolation on random hypergraphs

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