Hostname: page-component-6898cfcb55-th4rj Total loading time: 0 Render date: 2026-11-11T10:15:52.584Z Has data issue: false hasContentIssue false
  • English
  • Français

Jigsaw percolation on random hypergraphs

Part of:Graph theorySpecial processesCombinatorial probability

Published online by Cambridge University Press:  30 November 2017

Béla Bollobás,
Oliver Cooley,
Mihyun Kang and
Christoph Koch
Béla Bollobás*
Affiliation:
University of Cambridge, University of Memphis, and London Institute for Mathematical Sciences
Oliver Cooley*
Affiliation:
Graz University of Technology
Mihyun Kang*
Affiliation:
Graz University of Technology
Christoph Koch*
Affiliation:
Graz University of Technology
*
* Postal address: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, UK. Email address: b.bollobas@dpmms.cam.ac.uk
** Postal address: Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria.
** Postal address: Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria.
*****Current address:Mathematics Institute,University of Warwick,Zeeman Building,CV4 7AL Coventry,UK.Email address:c.koch@warwick.ac.uk
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Keywords

Jigsaw percolationrandom graphhypergraphhigh-order connectednessbreadth-first search

MSC classification

Primary:05C80: Random graphs
Secondary:60K35: Interacting random processes; statistical mechanics type models; percolation theory05C65: Hypergraphs60C05: Combinatorial probability

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 4 , December 2017, pp. 1261 - 1277
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Ball, P. (2014). Crowd-sourcing: strength in numbers. Nature 506, 422–423. CrossRefGoogle ScholarPubMed
[2] Barabási, A. L. et al. (2002). Evolution of the social network of scientific collaborations. Phys. A 311, 590–614. CrossRefGoogle Scholar
[3] Bollobás, B., Riordan, O., Slivken, E. and Smith, P. (2017). The threshold for jigsaw percolation on random graphs. Electron. J. Combin. 24, 2.36. CrossRefGoogle Scholar
[4] Brummitt, C. D., Chatterjee, S., Dey, P. S. and Sivakoff, D. (2015). Jigsaw percolation: what social networks can collaboratively solve a puzzle? Ann. Appl. Prob. 25, 2013–2038. CrossRefGoogle Scholar
[5] Cooley, O., Kang, M. and Koch, C. (2016). Threshold and hitting time for high-order connectedness in random hypergraphs. Electron. J. Combin. 23, 2.48. CrossRefGoogle Scholar
[6] Gravner, J. and Sivakoff, D. (2017). Nucleation scaling in jigsaw percolation. Ann. Appl. Prob. 27, 395–438. CrossRefGoogle Scholar
[7] Gutiérrez Sanchez, A. (2017). Multi-colored jigsaw percolation on random graphs. Master's Thesis. Graz University of Technology. Google Scholar
[8] Newman, M. E. J. (2001). Scientific collaboration networks. I. Network construction and fundamental results. Phys. Rev. E 64, 016131. CrossRefGoogle ScholarPubMed
[9] Newman, M. E. J. (2001). Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Phys. Rev. E 64, 016132. CrossRefGoogle ScholarPubMed
[10] Newman, M. E. J. (2001). The structure of scientific collaboration networks. Proc. Nat. Acad. Sci. USA 98, 404–409. CrossRefGoogle ScholarPubMed
[11] Tebbe, J. (2011). Book review: Where good ideas come from: the natural history of innovation. J. Psychological Issues Organizational Culture 2, 106–110. CrossRefGoogle Scholar