Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph

DOI10.1007/S10955-021-02819-WMaRDI QIDQ2060004zbMATHOpenAlexFDO

Authors Omer Angel, Brett Kolesnik

Publication date 13 December 2021

Published in Journal of Statistical Physics (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionlarge deviationsrandom graphsbootstrap percolationdiscrete calculus of variations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We study atypical behavior in bootstrap percolation on the ErdH{o}s-R'enyi random graph. Initially a set $S$ is infected. Other vertices are infected once at least $r$ of their neighbors become infected. Janson et al. (2012) locates the critical size of $S$, above which it is likely that the infection will spread almost everywhere. Below this threshold, a central limit theorem is proved for the size of the eventually infected set. In this note, we calculate the rate function for the event that a small set $S$ eventually infects an unexpected number of vertices, and identify the least-cost trajectory realizing such a large deviation.

Recommendations

• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
• Bootstrap percolation on \(G(n,p)\) revisited
• Majority bootstrap percolation on \(G(n,p)\)
• Sharp thresholds for contagious sets in random graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3912791 (Why is no real title available?)
• scientific article; zbMATH DE number 124800 (Why is no real title available?)
• scientific article; zbMATH DE number 1515079 (Why is no real title available?)
• scientific article; zbMATH DE number 949124 (Why is no real title available?)
• scientific article; zbMATH DE number 1407641 (Why is no real title available?)
• scientific article; zbMATH DE number 3046890 (Why is no real title available?)
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
• Asymptotic final-size distribution for some chain-binomial processes
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Contagious sets in expanders
• Contagious sets in random graphs
• Discrete calculus of variations
• Equivalence of discrete Euler equations and discrete Hamiltonian systems
• Graph bootstrap percolation
• Metastability effects in bootstrap percolation
• Minimal contagious sets in random regular graphs
• Minimal percolating sets in bootstrap percolation
• On the asymptotic distribution of the size of a stochastic epidemic
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Sharp thresholds for contagious sets in random graphs
• Solving Ordinary Differential Equations I
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(5)

• Weakly saturated random graphs
• Bootstrap percolation on the stochastic block model
• The sharp \(K_4\)-percolation threshold on the Erdős-Rényi random graph
• Large deviations of the greedy independent set algorithm on sparse random graphs
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)

This page was built for publication: Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph

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