Majority Bootstrap Percolation on the Hypercube
From MaRDI portal
Abstract: In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A subset V(G), are normally chosen independently at random, each with probability p, say. This process has been extensively studied on the sequence of torus graphs [n]^d, for n = 1,2,..., where d = d(n) is either fixed or a very slowly growing function of n. For example, Cerf and Manzo showed that the critical probability is o(1) if d(n) < log*(n), i.e., if p = p(n) is bounded away from zero then the probability of percolation on [n]^d tends to one as n goes to infinity. In this paper we study the case when the growth of d to infinity is not excessively slow; in particular, we show that the critical probability is 1/2 + o(1) if d > (loglog(n))^2 logloglog(n), and give much stronger bounds in the case that G is the hypercube, [2]^d.
Recommendations
- Majority bootstrap percolation on \(G(n,p)\)
- Bootstrap percolation on the hypercube
- Percolation in High Dimensions
- Hypercube percolation
- The giant component after percolation of product graphs
- Supercritical site percolation on the hypercube: small components are small
- Slightly subcritical hypercube percolation
- scientific article; zbMATH DE number 1369842
- Extremal bounds for bootstrap percolation in the hypercube
- Extremal bounds for bootstrap percolation in the hypercube
Cites work
- A logical calculus of the ideas immanent in nervous activity
- Asymptotic expansions inn−1 for percolation critical values on then-Cube and ℤn
- Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
- Bootstrap percolation on the hypercube
- Bootstrap percolation on the random regular graph
- Evolution of the n-cube
- Expansion in ${\boldsymbol{n^{-1}}}$ for Percolation Critical Values on the $n$-cube and ${\boldsymbol{{\mathbb Z}^n}}$: the First Three Terms
- Finite size scaling in three-dimensional bootstrap percolation
- Hypercubic Sorting Networks
- Largest random component of a k-cube
- Metastability effects in bootstrap percolation
- On the behavior of some cellular automata related to bootstrap percolation
- Random subgraphs of finite graphs. III: The phase transition for the n-cube
- Sharp metastability threshold for two-dimensional bootstrap percolation
- Stretched exponential fixation in stochastic Ising models at zero temperature
- The Evolution of Random Subgraphs of the Cube
- The threshold regime of finite volume bootstrap percolation.
Cited in
(43)- Metastable behavior for bootstrap percolation on regular trees
- Rates for the probability of large cubes being non-internally spanned in modified bootstrap percolation
- Sharp thresholds for contagious sets in random graphs
- A cube dismantling problem related to bootstrap percolation
- Triggering cascades on undirected connected graphs
- A note on the majority dynamics in inhomogeneous random graphs
- Anisotropic bootstrap percolation in three dimensions
- Majority rule cellular automata
- Bootstrap percolation on the Hamming torus
- Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
- Bootstrap percolation, and other automata
- Unlacing hypercube percolation: a survey
- Strict majority bootstrap percolation in the \textit{r}-wheel
- Graph bootstrap percolation
- The diameter of a random subgraph of the hypercube
- Sharp metastability threshold for an anisotropic bootstrap percolation model
- New bounds for contagious sets
- A sharper threshold for bootstrap percolation in two dimensions
- Bootstrap percolation in high dimensions
- Majority bootstrap percolation on \(G(n,p)\)
- Rumor spreading: A trigger for proliferation or fading away
- A note on bootstrap percolation thresholds in plane tilings using regular polygons
- Hypercube percolation
- Monotone cellular automata in a random environment
- The sharp threshold for bootstrap percolation in all dimensions
- Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
- Color War: Cellular Automata with Majority-Rule
- Extremal bounds for bootstrap percolation in the hypercube
- Extremal bounds for bootstrap percolation in the hypercube
- Universality for two‐dimensional critical cellular automata
- Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
- On the running time of hypergraph bootstrap percolation
- On dissemination thresholds in regular and irregular graph classes
- Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
- A branching process with deletions and mergers that matches the threshold for hypercube percolation
- Bootstrap percolation on the high-dimensional Hamming graph
- Bootstrap percolation on the random graph \(G_{n,p}\)
- Majority dynamics: the power of one
- Majority bootstrap percolation on the permutahedron and other high-dimensional graphs
- Bootstrap percolation on the hypercube
- Bootstrap percolation in three dimensions
- The survival of large dimensional threshold contact processes
- Random graph asymptotics on high-dimensional tori
This page was built for publication: Majority Bootstrap Percolation on the Hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3557503)
