Minimum degree conditions for small percolating sets in bootstrap percolation

DOI10.37236/6937MaRDI QIDQ2185227zbMATH OpenOpenAlexFDO

Authors Karen Gunderson

Publication date 4 June 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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

zbMATH Keywords

bootstrap percolationpercolating sets

Mathematics Subject Classification ID

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

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.

Review text

Summary: 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 percolate if eventually all vertices are infected. For every \(r \geq 3\), 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 \(\lfloor n/2 \rfloor +1\) has a percolating set of size \(3\) and for \(r \geq 4\) and \(n\) large enough (in terms of \(r)\), every graph on \(n\) vertices with minimum degree \(\lfloor n/2 \rfloor + (r-3)\) has a percolating set of size \(r\). A class of examples are given to show the sharpness of these results.

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

Cites work

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

Cited in

(10)

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

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)