Minimum degree conditions for small percolating sets in bootstrap percolation

DOI10.37236/6937zbMATH Open1441.60080arXiv1703.10741OpenAlexW3028781085MaRDI QIDQ2185227FDOQ2185227

Authors: Karen Gunderson 

Publication date: 4 June 2020

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The $r$-neighbour bootstrap process is an update rule for the states of vertices in which `uninfected' vertices with at least $r$ `infected' neighbours become infected and a set of initially infected vertices is said to emph{percolate} if eventually all vertices are infected. For every $rgeq3$, a sharp condition is given for the minimum degree of a sufficiently large graph that guarantees the existence of a percolating set of size $r$. In the case $r=3$, for $n$ large enough, any graph on $n$ vertices with minimum degree $lfloorn/2floor+1$ has a percolating set of size $3$ and for $rgeq4$ and $n$ large enough (in terms of $r$), every graph on $n$ vertices with minimum degree $lfloorn/2floor+(r-3)$ has a percolating set of size $r$. A class of examples are given to show the sharpness of these results.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Ore and Chvátal-type degree conditions for bootstrap percolation from small sets
• Extremal bounds for bootstrap percolation in the hypercube
• Extremal bounds for bootstrap percolation in the hypercube
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Largest and smallest minimal percolating sets in trees

zbMATH Keywords

bootstrap percolationpercolating sets

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Extremal problems in graph theory (05C35)

Cites Work

• On a problem of K. Zarankiewicz
• Largest and smallest minimal percolating sets in trees
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• Bootstrap percolation in high dimensions
• Bootstrap percolation on the hypercube
• Random disease on the square grid
• Minimal percolating sets in bootstrap percolation
• New bounds for contagious sets
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Linear algebra and bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Minimal contagious sets in random regular graphs
• Contagious sets in expanders
• Contagious sets in random graphs
• Lower bounds for graph bootstrap percolation via properties of polynomials
• Smallest percolating sets in bootstrap percolation on grids
• Ore and Chvátal-type degree conditions for bootstrap percolation from small sets

Cited In (8)

• Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs
• Active influence spreading in social networks
• Largest and smallest minimal percolating sets in trees
• Deterministic bootstrap percolation on trees
• Lower bounds for graph bootstrap percolation via properties of polynomials
• On the spread of influence in graphs
• Ore and Chvátal-type degree conditions for bootstrap percolation from small sets
• Bootstrap percolation in strong products of graphs

This page was built for publication: Minimum degree conditions for small percolating sets in bootstrap percolation

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