Bootstrap percolation in random k-uniform hypergraphs

DOI10.1016/J.ENDM.2015.06.081MaRDI QIDQ322332zbMATH OpenOpenAlexFDO

Authors Mihyun Kang, Christoph Koch, Tamás Makai

Publication date 14 October 2016

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

zbMATH Keywords

branching processbootstrap percolationrandom hypergraph

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(12)

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

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)