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

DOI10.1007/S10955-021-02819-WzbMATH Open1490.60259arXiv1705.06815OpenAlexW3206499172MaRDI QIDQ2060004FDOQ2060004

Authors: Omer Angel, Brett Kolesnik 

Publication date: 13 December 2021

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

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.

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

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}\)

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)

Cites Work

• Title not available (Why is that?)
• Solving Ordinary Differential Equations I
• Title not available (Why is that?)
• On the asymptotic distribution of the size of a stochastic epidemic
• Asymptotic final-size distribution for some chain-binomial processes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the behavior of some cellular automata related to bootstrap percolation
• Equivalence of discrete Euler equations and discrete Hamiltonian systems
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Metastability effects in bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Title not available (Why is that?)
• Minimal percolating sets in bootstrap percolation
• Graph bootstrap percolation
• Minimal contagious sets in random regular graphs
• Title not available (Why is that?)
• Discrete calculus of variations
• Title not available (Why is that?)
• Contagious Sets in Expanders
• Sharp thresholds for contagious sets in random graphs
• Contagious sets in random graphs
• Contagious sets in dense graphs
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)

Cited In (4)

• Weakly saturated random graphs
• Bootstrap percolation on the stochastic block model
• Large deviations of the greedy independent set algorithm on sparse random graphs
• The sharp \(K_4\)-percolation threshold on the Erdős-Rényi random graph

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)