Jigsaw percolation on random hypergraphs. (30th November 2017)

• Record Type: Journal Article
• Authors: Bollobás, Béla; Cooley, Oliver; Kang, Mihyun; Koch, Christoph
• Is Part Of: Journal of applied probability. Volume 54:Number 4(2017)
• Page Start: 1261
• Page End: 1277
• Publication Date: 2017-11-30
• Subjects: Jigsaw percolation, -- random graph, -- hypergraph, -- high-order connectedness, -- breadth-first search; Primary 05C80, -- Secondary 60K35, -- 05C65, -- 60C05; 519.2
• DOI: 10.1017/jpr.2017.62
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: The jigsaw percolation process on graphs was introduced by Brummitt et al. (2015) 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ás et al. (2017) 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.