A sharp threshold for bootstrap percolation in a random hypergraph

DOI10.1214/21-EJP650zbMATH Open1479.60199arXiv1806.02903OpenAlexW3173681176MaRDI QIDQ2042875FDOQ2042875

Authors: Natasha Morrison, Jonathan A. Noel 

Publication date: 21 July 2021

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: Given a hypergraph $mathcalH$, the $mathcalH$-bootstrap process starts with an initial set of infected vertices of $mathcalH$ and, at each step, a healthy vertex $v$ becomes infected if there exists a hyperedge of $mathcalH$ in which $v$ is the unique healthy vertex. We say that the set of initially infected vertices percolates if every vertex of $mathcalH$ is eventually infected. We show that this process exhibits a sharp threshold when $mathcalH$ is a hypergraph obtained by randomly sampling hyperedges from an approximately $d$-regular $r$-uniform hypergraph satisfying some mild degree and codegree conditions; this confirms a conjecture of Morris. As a corollary, we obtain a sharp threshold for a variant of the graph bootstrap process for strictly $2$-balanced graphs which generalises a result of Kor'{a}ndi, Peled and Sudakov. Our approach involves an application of the differential equations method.

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

Recommendations

• Bootstrap percolation in random \(k\)-uniform hypergraphs
• Graph bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on G(n,p) revisited
• Sharp thresholds in bootstrap percolation

zbMATH Keywords

martingaleshypergraphsbootstrap percolationsharp thresholddifferential equations method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Hypergraphs (05C65)

Cites Work

• On tail probabilities for martingales
• Title not available (Why is that?)
• The triangle-free process
• A note on the random greedy independent set algorithm
• Concentration of Measure for the Analysis of Randomized Algorithms
• Title not available (Why is that?)
• The triangle-free process and the Ramsey number \(R(3,k)\)
• The early evolution of the \(H\)-free process
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Finite size scaling in three-dimensional bootstrap percolation
• Differential equations for random processes and random graphs
• Bootstrap percolation in power-law random graphs
• The threshold regime of finite volume bootstrap percolation.
• Metastability effects in bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• Concentration of multivariate polynomials and its applications
• Bootstrap percolation in living neural networks
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation in three dimensions
• Poisson approximation for large deviations
• Concentration of non‐Lipschitz functions and applications
• Title not available (Why is that?)
• An extremal problem for sets with applications to graph theory
• Title not available (Why is that?)
• Linear algebra and bootstrap percolation
• Random Graph Processes with Degree Restrictions
• Graph bootstrap percolation
• Exact bounds for some hypergraph saturation problems
• A natural barrier in random greedy hypergraph matching
• The time of graph bootstrap percolation
• Hyperconnectivity of graphs
• On the method of typical bounded differences
• Saturation in the hypercube and bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Random graph processes with maximum degree 2
• The sharp threshold for making squares
• Sharp thresholds for contagious sets in random graphs
• A random triadic process

Cited In (6)

• The time of bootstrap percolation with dense initial sets for all thresholds
• Weak saturation numbers of complete bipartite graphs in the clique
• On the running time of hypergraph bootstrap percolation
• Bootstrap percolation in random \(k\)-uniform hypergraphs
• A sharp threshold for a modified bootstrap percolation with recovery
• Strict majority bootstrap percolation in the \textit{r}-wheel

This page was built for publication: A sharp threshold for bootstrap percolation in a random hypergraph

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