Bootstrap percolation on a graph with random and local connections

DOI10.1007/S10955-015-1294-XMaRDI QIDQ887085zbMATH OpenOpenAlexFDO

Authors Tatyana S. Turova, Thomas Vallier

Publication date 28 October 2015

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

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

zbMATH Keywords

bootstrap percolationphase transitionrandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Critical phenomena in equilibrium statistical mechanics (82B27) Percolation (82B43)

Abstract: Let $G_{n,p}^1$ be a superposition of the random graph $G_{n,p}$ and a one-dimensional lattice: the $n$ vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability $p$ between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realisation of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $rgeq2$ active neighbours become active as well. We study the size of the final active set in the limit when $nightarrowinfty$. The parameters of the model are $n$, the size $A_0=A_0(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. Bootstrap percolation process on $G_{n,p}$ was studied earlier. Here we show that the addition of $n$ local connections to the graph $G_{n,p}$ leads to a more narrow critical window for the phase transition, preserving however, the critical scaling of parameters known for the model on $G_{n,p}$. We discover a range of parameters which yields percolation on $G_{n,p}^1$ but not on $G_{n,p}$.

Recommendations

• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Bootstrap percolation on \(G(n,p)\) revisited
• A modified bootstrap percolation on a random graph coupled with a lattice
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)

Cites work

• A note on the micromechanics of plastic yield of porous solids
• An improved upper bound for bootstrap percolation in all dimensions
• Bootstrap percolation on Galton-Watson trees
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Merging percolation onZdand classical random graphs: Phase transition
• Nucleation scaling in jigsaw percolation
• On percolation in random graphs with given vertex degrees
• Phase transitions in the neuropercolation model of neural populations with mixed local and non-local interactions
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(11)

• Local bootstrap percolation
• A modified bootstrap percolation on a random graph coupled with a lattice
• A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
• Accelerated information dissemination on networks with local and global edges
• Bootstrap percolation on the stochastic block model
• \(K_{r,s}\) graph bootstrap percolation
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation on the random regular graph
• Remarks on bootstrap percolation in metric networks
• Bootstrap Percolation on Degenerate Graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)

This page was built for publication: Bootstrap percolation on a graph with random and local connections

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