Bootstrap percolation in random k-uniform hypergraphs

DOI10.1016/J.ENDM.2015.06.081zbMATH Open1346.05273arXiv1704.07144OpenAlexW2210208272MaRDI QIDQ322332FDOQ322332

Authors: Mihyun Kang, Christoph Koch, Tamás Makai 

Publication date: 14 October 2016

Abstract: We investigate bootstrap percolation with infection threshold $r>1$ on the binomial $k$-uniform random hypergraph $H_k(n,p)$ in the regime $n^{-1}ll{n}^{k-2}pll{n}^{-1/r}$, when the initial set of infected vertices is chosen uniformly at random from all sets of given size. We establish a threshold such that if there are less vertices in the initial set of infected vertices, then whp only a few additional vertices become infected, while if the initial set of infected vertices exceeds the threshold then whp almost every vertex becomes infected. In addition, for $k=2$, we show that the probability of failure decreases exponentially.

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

Recommendations

• A sharp threshold for bootstrap percolation in a random hypergraph
• Bootstrap percolation on G(n,p) revisited
• Graph bootstrap percolation
• Sharp thresholds for contagious sets in random graphs
• The sharp threshold for bootstrap percolation in all dimensions

zbMATH Keywords

branching processbootstrap percolationrandom hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Cites Work

• Connected components in random graphs with given expected degree sequences
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Bootstrap percolation in power-law random graphs
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation in living neural networks
• Bootstrap percolation on the random graph \(G_{n,p}\)

Cited In (11)

• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• On \(K_{2, t}\)-bootstrap percolation
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• On connectivity, conductance and bootstrap percolation for a random \(K\)-out, age-biased graph
• On the running time of hypergraph bootstrap percolation
• \(K_{r,s}\) graph bootstrap percolation
• Bootstrap percolation on the hypercube
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Strict majority bootstrap percolation in the \textit{r}-wheel
• Bootstrap percolation on the random regular graph
• A sharp threshold for bootstrap percolation in a random hypergraph

This page was built for publication: Bootstrap percolation in random \(k\)-uniform hypergraphs

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