ID: 1507.07997

A modified bootstrap percolation on a random graph coupled with a lattice

July 29, 2015

View on ArXiv

Similar papers 2

Merging percolation on $Z^d$ and classical random graphs: Phase transition

December 21, 2006

87% Match
Tatyana S. Turova, Thomas Vallier
Probability

We study a random graph model which is a superposition of the bond percolation model on $Z^d$ with probability $p$ of an edge, and a classical random graph $G(n, c/n)$. We show that this model, being a {\it homogeneous} random graph, has a natural relation to the so-called "rank 1 case" of {\it inhomogeneous} random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe the phase diagram on the set of parameters $c\geq 0$ and $0 \l...

Find SimilarView on arXiv

Universal behaviour of majority bootstrap percolation on high-dimensional geometric graphs

June 25, 2024

87% Match
Maurício Collares, Joshua Erde, ... , Kang Mihyun
Combinatorics
Probability

Majority bootstrap percolation is a monotone cellular automata that can be thought of as a model of infection spreading in networks. Starting with an initially infected set, new vertices become infected once more than half of their neighbours are infected. The average case behaviour of this process was studied on the $n$-dimensional hypercube by Balogh, Bollob\'{a}s and Morris, who showed that there is a phase transition as the typical density of the initially infected set in...

Find SimilarView on arXiv

Bootstrap Percolation on Random Geometric Graphs

January 13, 2012

87% Match
Milan Bradonjić, Iraj Saniee
Probability
Discrete Mathematics

Bootstrap percolation has been used effectively to model phenomena as diverse as emergence of magnetism in materials, spread of infection, diffusion of software viruses in computer networks, adoption of new technologies, and emergence of collective action and cultural fads in human societies. It is defined on an (arbitrary) network of interacting agents whose state is determined by the state of their neighbors according to a threshold rule. In a typical setting, bootstrap per...

Find SimilarView on arXiv

Recent advances and open challenges in percolation

April 21, 2014

87% Match
N. A. M. Araújo, P. Grassberger, B. Kahng, ... , Ziff R. M.
Statistical Mechanics

Percolation is the paradigm for random connectivity and has been one of the most applied statistical models. With simple geometrical rules a transition is obtained which is related to magnetic models. This transition is, in all dimensions, one of the most robust continuous transitions known. We present a very brief overview of more than 60 years of work in this area and discuss several open questions for a variety of models, including classical, explosive, invasion, bootstrap...

Find SimilarView on arXiv

Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time

March 25, 2009

87% Match
Markus Heydenreich, der Hofstad Remco van
Probability
Mathematical Physics

For critical bond-percolation on high-dimensional torus, this paper proves sharp lower bounds on the size of the largest cluster, removing a logarithmic correction in the lower bound in Heydenreich and van der Hofstad (2007). This improvement finally settles a conjecture by Aizenman (1997) about the role of boundary conditions in critical high-dimensional percolation, and it is a key step in deriving further properties of critical percolation on the torus. Indeed, a criterion...

Find SimilarView on arXiv

The second term for two-neighbour bootstrap percolation in two dimensions

June 23, 2018

86% Match
Ivailo Hartarsky, Robert Morris
Probability
Combinatorics

In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid-glass transition, the most extensively-studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major ...

Find SimilarView on arXiv

Merging percolation and classical random graphs: Phase transition in dimension 1

September 21, 2006

86% Match
Tatyana S. Turova, Thomas Vallier
Probability

We study a random graph model which combines properties of the edge percolation model on Z^d and a classical random graph G(n,c/n). We show that this model, being a homogeneous random graph, has a natural relation to the so-called "rank 1 case" of inhomogeneous random graphs. This allows us to use the newly developed theory of inhomogeneous random graphs to describe completely the phase diagram in the case d=1. The phase transition is similar to the classical random graph, it...

Find SimilarView on arXiv

Bootstrap percolation on the Hamming torus with threshold 2

July 9, 2014

86% Match
Erik Slivken
Probability

This paper analyzes various questions pertaining to bootstrap percolation on the $d$-dimensional Hamming torus where each node is open with probability $p$ and the percolation threshold is 2. For each $d'<d$ we find the critical exponent for the event that a $d'$-dimensional subtorus becomes open and compute the limiting value of its probability under the critical scaling. For even $d'$, we use the Chen-Stein method to show that the number of $d'$-dimensional subtori that bec...

Find SimilarView on arXiv

Bootstrap percolation in high dimensions

July 17, 2009

86% Match
Jozsef Balogh, Bela Bollobas, Robert Morris
Probability
Combinatorics

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine...

Find SimilarView on arXiv

Bootstrap percolation in random geometric graphs

October 23, 2021

86% Match
Victor Falgas-Ravry, Amites Sarkar
Probability
Combinatorics

Following Bradonji\'c and Saniee, we study a model of bootstrap percolation on the Gilbert random geometric graph on the $2$-dimensional torus. In this model, the expected number of vertices of the graph is $n$, and the expected degree of a vertex is $a\log n$ for some fixed $a>1$. Each vertex is added with probability $p$ to a set $A_0$ of initially infected vertices. Vertices subsequently become infected if they have at least $ \theta a \log n $ infected neighbours. Here $p...

Find SimilarView on arXiv