A sharp threshold for bootstrap percolation in a random hypergraph

DOI10.1214/21-EJP650MaRDI QIDQ2042875zbMATHOpenAlexFDO

Authors Natasha Morrison, Jonathan A. Noel

Publication date 21 July 2021

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

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

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)

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.

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

Cites work

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

Cited in

(6)

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

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)