Finite-Size Effects for Anisotropic Bootstrap Percolation: Logarithmic Corrections

In this note we analyse an anisotropic, two-dimensional bootstrap percolation model introduced by Gravner and Griffeath. We present upper and lower bounds on the finite-size effects. We discuss the similarities with the semi-oriented model introduced by Duarte.     

Bootstrap Percolation in Power-Law Random Graphs

A bootstrap percolation process on a graph $G$ is an “infection” process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $r$ infected neighbours becomes infected and remains so forever. The parameter $r\ge 2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse this process in the case where the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are $a(n)$ randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent $\beta $ , where $2 < \beta < 3$ , then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function $a_c(n)$ such that $a_c(n) = o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n) \ll a_c(n)$ , then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)\gg a_c(n)$ , then there is a constant $\varepsilon > 0$ such that, with high probability, the final set of infected vertices has size at least $\varepsilon n$ . This behaviour is in sharp contrast with the case where the underlying graph is a $G(n, p)$ random graph with $p=d/n$ . It follows from an observation of Balogh and Bollobás that in this case if the number of initially infected vertices is sublinear, then there is lack of evolution of the process. It turns out that when the maximum degree is $o(n^{1/(\beta - 1)})$ , then $a_c(n)$ depends also on $r$ . But when the maximum degree is $\Theta (n^{1/(\beta - 1)})$ , then $a_c (n) = n^{\beta - 2 \over \beta - 1}$ .     

Bootstrap Percolation in Living Neural Networks

Recent experimental studies of living neural networks reveal that their global activation induced by electrical stimulation can be explained using the concept of bootstrap percolation on a directed random network. The experiment consists in activating externally an initial random fraction of the neurons and observe the process of firing until its equilibrium. The final portion of neurons that are active depends in a non linear way on the initial fraction. The main result of this paper is a theorem which enables us to find the final proportion of the fired neurons, in the asymptotic case, in the case of random directed graphs with given node degrees as the model for interacting network. This gives a rigorous mathematical proof of a phenomena observed by physicists in neural networks.     

Scaling Limit and Critical Exponents for Two-Dimensional Bootstrap Percolation

Consider a cellular automaton with state space {0,1} ² where the initial configuration _0 is chosen according to a Bernoulli product measure, 1s are stable, and 0s become 1s if they are surrounded by at least three neighboring 1s. In this paper we show that the configuration _n at time n converges exponentially fast to a final configuration , and that the limiting measure corresponding to is in the universality class of Bernoulli (independent) percolation. More precisely, assuming the existence of the critical exponents , , and , and of the continuum scaling limit of crossing probabilities for independent site percolation on the close-packed version of ² (i.e. for independent *-percolation on ), we prove that the bootstrapped percolation model has the same scaling limit and critical exponents.This type of bootstrap percolation can be seen as a paradigm for a class of cellular automata whose evolution is given, at each time step, by a monotonic and nonessential enhancement [Aizenman and Grimmett, J. Stat. Phys. 63: 817--835 (1991); Grimmett, Percolation, 2nd Ed. (Springer, Berlin, 1999)     

A Note on Anisotropic Percolation

We consider an anisotropic independent bond percolation model on , i.e. we suppose that the vertical edges of are open with probability p and closed with probability 1–p, while the horizontal edges of are open with probability p and closed with probability 1– p, with 0 < p, < 1. Let , with x₁ < x₂, and . It is natural to ask how the two point connectivity function P_p,({0 x}) behaves, and whether anisotropy in percolation probabilities implies the strict inequality P_p,({0 x})> P_p,({0 x}). In this note we give affirmative answer at least for some regions of the parameters involved.Mathematics Subject Classifications (2000). 82B20, 82B41, 82B43.     

Percolation Thresholds and Phase Transitions in Binary Composites

The metal–insulator and metal–superconductor phase transitions related to the percolation thresholds in two-component composites are considered. The behavior of effective conductivity σ _e in the vicinity of both thresholds is described in terms of the similarity hypothesis. A one-to-one correspondence between the equations derived for σ _e in both critical regions is found for randomly heterogeneous systems.     

A Sharp Threshold for a Modified Bootstrap Percolation with Recovery

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected.     

A Cube Dismantling Problem Related to Bootstrap Percolation

An n×n×?×n hypercube is made from n ^d unit hypercubes. Two unit hypercubes are neighbours if they share a (d?1)-dimensional face. In each step of a dismantling process, we remove a unit hypercube that has precisely d neighbours. A move is balanced if the neighbours are in d orthogonal directions. In the extremal case, there are n ^d?1 independent unit hypercubes left at the end of the dismantling. We call this set of hypercubes a solution. If a solution is projected in d orthogonal directions and we get the entire [n] ^d?1 hypercube in each direction, then the solution is perfect. We show that it is possible to use a greedy algorithm to test whether a set of hypercubes forms a solution. Perfect solutions turn out to be precisely those which can be reached using only balanced moves. Every perfect solution corresponds naturally to a Latin hypercube. However, we show that almost all Latin hypercubes do not correspond to solutions. In three dimensions, we find at least n perfect solutions for every n, and we use our greedy algorithm to count the perfect solutions for n??6. We also construct an infinite family of imperfect solutions and show that the total size of its three orthogonal projections is asymptotic to the minimum possible value. Our results solve several conjectures posed in a proceedings paper by Barát, Korondi and Varga. If our dismantling process is reversed we get a build-up process very closely related to well-studied models of bootstrap percolation. We show that in an important special case our build-up reaches the same maximal position as bootstrap percolation.     

Bootstrap Percolation and Kinetically Constrained Models on Hyperbolic Lattices

We study bootstrap percolation (BP) on hyperbolic lattices obtained by regular tilings of the hyperbolic plane. Our work is motivated by the connection between the BP transition and the dynamical transition of kinetically constrained models, which are in turn relevant for the study of glass and jamming transitions. We show that for generic tilings there exists a BP transition at a nontrivial critical density, 0<ρ _c <1. Thus, despite the presence of loops on all length scales in hyperbolic lattices, the behavior is very different from that on Euclidean lattices where the critical density is either zero or one. Furthermore, we show that the transition has a mixed character since it is discontinuous but characterized by a diverging correlation length, similarly to what happens on Bethe lattices and random graphs of constant connectivity.     

The Central Limit Theorem for Supercritical Oriented Percolation in Two Dimensions

We consider the cardinality of supercritical oriented bond percolation in two dimensions. We show that, whenever the the origin is conditioned to percolate, the process appropriately normalized converges asymptotically in distribution to the standard normal law. This resolves a longstanding open problem pointed out to in several instances in the literature. The result applies also to the continuous-time analog of the process, viz. the basic one-dimensional contact process. We also derive general random-indices central limit theorems for associated random variables as byproducts of our proof.     

A Remark Concerning Percolation Thresholds in Polydisperse Systems of Finite-Diameter Rods

A lattice-based analysis of the percolation threshold for randomly distributed cylindrical particles is generalized to consider arbitrary joint distributions over the radii and lengths of the rods. Effects due to the finite hard core diameter of the particles are accounted for. An analogy to site percolation on a modified Bethe lattice is exploited to yield a result for the percolation threshold that is equivalent to one that has been obtained from integral equation methods in the limit of large aspect ratios for the rods.     

Truncated Connectivities in a Highly Supercritical Anisotropic Percolation Model

We consider an anisotropic bond percolation model on $\mathbb{Z}^{2}$ , with p=(p _h ,p _v )∈[0,1]², p _v >p _h , and declare each horizontal (respectively vertical) edge of $\mathbb{Z}^{2}$ to be open with probability p _h (respectively p _v ), and otherwise closed, independently of all other edges. Let $x=(x_{1},x_{2}) \in\mathbb{Z}^{2}$ with 0<x ₁<x ₂, and $x'=(x_{2},x_{1})\in\mathbb{Z}^{2}$ . It is natural to ask how the two point connectivity function $\mathbb{P}_{\mathbf{p}}(\{0\leftrightarrow x\})$ behaves, and whether anisotropy in percolation probabilities implies the strict inequality $\mathbb{P}_{\mathbf{p}}(\{0\leftrightarrow x\})>\mathbb{P}_{\mathbf {p}}(\{0\leftrightarrow x'\})$ . In this note we give an affirmative answer in the highly supercritical regime.     

Rigorous Confidence Intervals on Critical Thresholds in 3 Dimensions

We extend the method of Balister, Bollobás and Walters (Phys. Rev. E 76:011110, 2007) for determining rigorous confidence intervals for the critical threshold of two dimensional lattices to three (and higher) dimensional lattices. We describe a method for determining a full confidence interval and apply it to show that the critical threshold for bond percolation on the simple cubic lattice is between \(0.2485\) and \(0.2490\) with \(99.9999\,\%\) confidence, and the critical threshold for site percolation on the same lattice is between \(0.3110\) and \(0.3118\) with \(99.9999\,\%\) confidence.     

Similarity of Percolation Thresholds on the HCP and FCC Lattices

Extensive Monte Carlo simulations were performed in order to determine the precise values of the critical thresholds for site (p ^hcp _{c, S} =0.199 255 5±0.000 001 0) and bond (p ^hcp _{c, B} =0.120 164 0±0.000 001 0) percolation on the hcp lattice to compare with previous precise measurements on the fcc lattice. Also, exact enumeration of the hcp and fcc lattices was performed and yielded generating functions and series for the zeroth, first, and second moments of both lattices. When these series and the values of p _c are compared to those for the fcc lattice, it is apparent that the site percolation thresholds are different; however, the bond percolation thresholds are equal within error bars, and the series only differ slightly in the higher order terms, suggesting the actual values are very close to each other, if not identical.     

Thresholds and Universality of the Site Percolation on the Sierpinski Carpets

Following the methods proposed by Yonezawa, Sakamoto and Hori, we have calculated the percolation thresholds P_c, their error bars ΔP_c, and the correlation length exponents v of a family of the Sierpinski carpets for the site percolation problems by making use of MonteCarlo simulations and finite size scaling. We have found the dependence of P_c and v on the fractal dimensionality D_f and the lacunarity. We ascertain that the site percolation problems on a family of Sierpinski carpets with central cutouts and different D belong to different universal classes, and those on Sierpinski carpets with same D_f but of different lacunarities belong to different universal classes.     

On the Anisotropic Walk on the Supercritical Percolation Cluster

We investigate in this work the asymptotic behavior of an anisotropic random walk on the supercritical cluster for bond percolation on ^d, d2. In particular we show that for small anisotropy the walk behaves in a ballistic fashion, whereas for strong anisotropy the walk is sub-diffusive. For arbitrary anisotropy, we also prove the directional transience of the walk and construct a renewal structure.     

Random Walk on the Incipient Infinite Cluster for Oriented Percolation in High Dimensions

We consider simple random walk on the incipient infinite cluster for the spread-out model of oriented percolation on . In dimensions d > 6, we obtain bounds on exit times, transition probabilities, and the range of the random walk, which establish that the spectral dimension of the incipient infinite cluster is , and thereby prove a version of the Alexander–Orbach conjecture in this setting. The proof divides into two parts. One part establishes general estimates for simple random walk on an arbitrary infinite random graph, given suitable bounds on volume and effective resistance for the random graph. A second part then provides these bounds on volume and effective resistance for the incipient infinite cluster in dimensions d > 6, by extending results about critical oriented percolation obtained previously via the lace expansion.     

Improved Lower Bounds for the Critical Probability of Oriented Bond Percolation in Two Dimensions

We present a coupled decreasing sequence of random walks on Z that dominate the edge process of oriented bond percolation in two dimensions. Using the concept of random walk in a strip, we describe an algorithm that generates an increasing sequence of lower bounds that converges to the critical probability of oriented percolation p_c. From the 7th term on, these lower bounds improve upon 0.6298, the best rigorous lower bound at present, establishing 0.63328 as a rigorous lower bound for p_c. Finally, a Monte Carlo simulation technique is presented; the use thereof establishes 0.64450 as a non-rigorous five-digit-precision (lower) estimate for p_c. Mathematics Subject Classification (1991): 60K35 Supported by CNPq (grant N.301637/91-1). Supported by a grant from CNPq.