Bond percolation critical probability bounds for three Archimedean lattices

Rigorous bounds for the bond percolation critical probability are determined for three Archimedean lattices: .7385 < p_c((3, 12²) bond) < .7449, .6430 < p_c((4, 6, 12) bond) < .7376, .6281 < p_c((4, 8²) bond) < .7201. Consequently, the bond percolation critical probability of the (3, 12²) lattice is strictly larger than those of the other ten Archimedean lattices. Thus, the (3, 12²) bond percolation critical probability is possibly the largest of any vertex‐transitive graph with bond percolation critical probability that is strictly less than one. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 507–518, 2002     

Sharp metastability threshold for two-dimensional bootstrap percolation

 In the bootstrap percolation model, sites in an L by L square are initially independently declared active with probability p. At each time step, an inactive site becomes active if at least two of its four neighbours are active. We study the behaviour as p→0 and L→∞ simultaneously of the probability I(L,p) that the entire square is eventually active. We prove that I(L,p)→1 if , and I(L,p)→0 if , where λ=π²/18. We prove the same behaviour, with the same threshold λ, for the probability J(L,p) that a site is active by time L in the process on the infinite lattice. The same results hold for the so-called modified bootstrap percolation model, but with threshold λ^′=π²/6. The existence of the thresholds λ,λ^′ settles a conjecture of Aizenman and Lebowitz [3], while the determination of their values corrects numerical predictions of Adler, Stauffer and Aharony [2]. Received: 12 May 2002 / Revised version: 12 August 2002 / Published online: 14 November 2002 Research funded in part by NSF Grant DMS-0072398 Mathematics Subject Classification (2000): Primary 60K35; Secondary 82B43 Key words or phrases: Bootstrap percolation – Cellular automaton – Metastability – Finite-size scaling     

Localization transition of <Emphasis Type="Italic">d</Emphasis>-friendly walkers

 Friendly walkers is a stochastic model obtained from independent one-dimensional simple random walks {S ^k _j } _j≥0 , k=1,2,…,d by introducing ``non-crossing condition': and ``reward for collisions' characterized by parameters . Here, the reward for collisions is described as follows. If, at a given time n, a site in ℤ is occupied by exactly m≥2 walkers, then the site increases the probabilistic weight for the walkers by multiplicative factor exp (β _m )≥1. We study the localization transition of this model in terms of the positivity of the free energy and describe the location and the shape of the critical surface in the (d−1)-dimensional space for the parameters . Received: 13 June 2002 / Revised version: 24 August 2002 Published online: 28 March 2003 Mathematics Subject Classification (2000): 82B41, 82B26, 82D60, 60G50 Key words or phrases: Random walks – Random surfaces – Lattice animals – Phase transitions – Polymers – Random walks     

The critical probability for random Voronoi percolation in the plane is 1/2

We study percolation in the following random environment: let Z be a Poisson process of constant intensity on ℝ², and form the Voronoi tessellation of ℝ² with respect to Z. Colour each Voronoi cell black with probability p, independently of the other cells. We show that the critical probability is 1/2. More precisely, if p>1/2 then the union of the black cells contains an infinite component with probability 1, while if p<1/2 then the distribution of the size of the component of black cells containing a given point decays exponentially. These results are analogous to Kesten's results for bond percolation in ℤ². The result corresponding to Harris' Theorem for bond percolation in ℤ² is known: Zvavitch noted that one of the many proofs of this result can easily be adapted to the random Voronoi setting. For Kesten's results, none of the existing proofs seems to adapt. The methods used here also give a new and very simple proof of Kesten's Theorem for ℤ²; we hope they will be applicable in other contexts as well. Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900 Research partially undertaken during a visit to the Forschungsinstitut für Mathematik, ETH Zürich, Switzerland     

Coexistence of the infinite (*) clusters: — A remark on the square lattice site percolation

Summary We show that the critical probability p _c is strictly greater than 1/2 for the square lattice site percolation.     

Enhanced interface repulsion from quenched hard–wall randomness

 We consider the harmonic crystal, or massless free field, , , that is the centered Gaussian field with covariance given by the Green function of the simple random walk on ℤ ^d . Our main aim is to obtain quantitative information on the repulsion phenomenon that arises when we condition to be larger than , is an IID field (which is also independent of ϕ), for every x in a large region , with N a positive integer and D a bounded subset of ℝ ^d . We are mostly motivated by results for given typical realizations of σ (quenched set–up), since the conditioned harmonic crystal may be seen as a model for an equilibrium interface, living in a (d+1)–dimensional space, constrained not to go below an inhomogeneous substrate that acts as a hard wall. We consider various types of substrate and we observe that the interface is pushed away from the wall much more than in the case of a flat wall as soon as the upward tail of σ ₀ is heavier than Gaussian, while essentially no effect is observed if the tail is sub–Gaussian. In the critical case, that is the one of approximately Gaussian tail, the interplay of the two sources of randomness, ϕ and σ, leads to an enhanced repulsion effect of additive type. This generalizes work done in the case of a flat wall and also in our case the crucial estimates are optimal Large Deviation type asymptotics as of the probability that ϕ lies above σ in D _N . Received: 6 February 2002 / Revised version: 23 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2000): 82B24, 60K35, 60G15 Keywords or phrases: Harmonic Crystal – Rough Substrate – Quenched and Annealed Models – Entropic Repulsion – Gaussian fields – Extrema of Random Fields – Large Deviations – Random Walks     

A Note About Critical Percolation on Finite Graphs

In this note we study the geometry of the largest component C₁\mathcal {C}_{1} of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137–184, 2005). There it is shown that this component is of size n ^2/3, and here we show that its diameter is n ^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886–1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus \mathbbZ_n^d\mathbb{Z}_{n}^{d} (with d large and n→∞) and the Hamming cube {0,1} ⁿ .     

Diffusive scaling of the spectral gap for the dilute Ising lattice-gas dynamics below the percolation threshold

We consider a conservative stochastic lattice-gas dynamics reversible with respect to the canonical Gibbs measure of the bond dilute Ising model on ℤ ^d at inverse temperature β. When the bond dilution density p is below the percolation threshold we prove that for any particle density and any β, with probability one, the spectral gap of the generator of the dyamics in a box of side L centered at the origin scales like L ⁻². Such an estimate is then used to prove a decay to equilibrium for local functions of the form where ε is positive and arbitrarily small and α = ? for d = 1, α=1 for d≥2. In particular our result shows that, contrary to what happes for the Glauber dynamics, there is no dynamical phase transition when β crosses the critical value β _c of the pure system. Received: 10 April 2000 / Revised version: 23 October 2000 / Published online: 5 June 2001     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

The Alexander-Orbach conjecture holds in high dimensions

We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior has been established, namely when the dimension d is large enough or when d>6 and the lattice is sufficiently spread out. We find that random walk on the IIC exhibits anomalous diffusion with the spectral dimension d_s=\frac43d_{s}=\frac{4}{3} , that is, p _t (x,x)=t ^−2/3+o(1). This establishes a conjecture of Alexander and Orbach (J. Phys. Lett. (Paris) 43:625–631, 1982). En route we calculate the one-arm exponent with respect to the intrinsic distance.     

Droplet growth for three-dimensional Kawasaki dynamics

 The goal of this paper is to describe metastability and nucleation for a local version of the three-dimensional lattice gas with Kawasaki dynamics at low temperature and low density. Let $\Lambda\subseteq{\mathbb Z}^3$ be a large finite box. Particles perform simple exclusion on $\Lambda$, but when they occupy neighboring sites they feel a binding energy $-U<0$ that slows down their dissociation. Along each bond touching the boundary of $\Lambda$ from the outside, particles are created with rate $\rho=e^{-\Delta\beta}$ and are annihilated with rate 1, where $\beta$ is the inverse temperature and $\D>0$ is an activity parameter. Thus, the boundary of $\Lambda$ plays the role of an infinite gas reservoir with density $\rho$. We consider the regime where $\Delta\in (U,3U)$ and the initial configuration is such that $\Lambda$ is empty. For large $\beta$, the system wants to fill $\Lambda$ but is slow in doing so. We investigate how the transition from empty to full takes place under the dynamics. In particular, we identify the size and shape of the critical droplet\/ and the time of its creation in the limit as $\beta\to\infty$. Received: 23 February 2002 / Revised version: 24 June 2002 / Published online: 24 October 2002 Mathematics Subject Classification (2000): 60K35, 82B43, 82C43, 82C80 Key words or phrases: Lattice gas – Kawasaki dynamics – Metastability – Critical droplet – Large deviations – Discrete isoperimetric inequalities     

Ornstein-Zernike theory for finite range Ising models above T c

 We derive a precise Ornstein-Zernike asymptotic formula for the decay of the two-point function 〈Σ₀Σ _x 〉_β in the general context of finite range Ising type models on ℤ ^d . The proof relies in an essential way on the a-priori knowledge of the strict exponential decay of the two-point function and, by the sharp characterization of phase transition due to Aizenman, Barsky and Fernández, goes through in the whole of the high temperature region β<β _c . As a byproduct we obtain that for every β<β _c , the inverse correlation length ξ_β is an analytic and strictly convex function of direction. Received: 10 January 2002 / Revised version: 19 June 2002 / Published online: 14 November 2002 Partly supported by Italian G. N. A. F. A, EC grant SC1-CT91-0695 and the University of Bologna. Funds for selected research topics. Partly supported by the ISRAEL SCIENCE FOUNDATION founded by The Israel Academy of Science and Humanities. Partly supported by the Swiss National Science Foundation grant #8220-056599. Mathematics Subject Classification (2000): 60F15, 60K15, 60K35, 82B20, 37C30 Key words or phrases: Ising model – Ornstein-Zernike decay of correlations – Ruelle operator – Renormalization – Local limit theorems     

Level set representation for the Gibbs states of the ferromagnetic ising model

Summary We prove the existence of a real valued random field with parameters in thed-dimensional cubic lattice, such that the distribution of the level set of this random field is a Gibbs state for the nearest neighbour ferromagnetic Ising model. Using this, we prove the continuity of the percolation probability with respect to the parameter (,h) in the uniqueness region except on the critical curve _c ={(,h _c ())}, whereh _c() is the critical level of the external field above which percolation takes place.Supported in part by JSPS, BiBoS, Grant in Aid for Cooperative research no. 62303006 and Grant in Aid for Scientific Research no. 63540168     

Critical percolation exploration path and SLE 6: a proof of convergence

It was argued by Schramm and Smirnov that the critical site percolation exploration path on the triangular lattice converges in distribution to the trace of chordal SLE ₆. We provide here a detailed proof, which relies on Smirnov’s theorem that crossing probabilities have a conformally invariant scaling limit (given by Cardy’s formula). The version of convergence to SLE ₆ that we prove suffices for the Smirnov–Werner derivation of certain critical percolation crossing exponents and for our analysis of the critical percolation full scaling limit as a process of continuum nonsimple loops. Research of Charles M.Newman was partially supported by the US NSF under grants DMS-01-04278 and DMS-06-06696.     

Asymptotic behavior of the critical probability for ρ-percolation in high dimensions

We consider oriented bond or site percolation on ℤ ^d ₊. In the case of bond percolation we denote by P _p the probability measure on configurations of open and closed bonds which makes all bonds of ℤ ^d ₊ independent, and for which P _p {e is open} = 1 −P _p e {is closed} = p for each fixed edge e of ℤ ^d ₊. We take X(e) = 1 (0) if e is open (respectively, closed). We say that ρ-percolation occurs for some given 0 < ρ≤ 1, if there exists an oriented infinite path v ₀ = 0, v ₁, v ₂, …, starting at the origin, such that lim inf _{n →∞} (1/n) ∑ _i=1 ⁿ X(e _i ) ≥ρ, where e _i is the edge {v _i−1 , v _i }. [MZ92] showed that there exists a critical probability p _c = p _c (ρ, d) = p _c (ρ, d, bond) such that there is a.s. no ρ-percolation for p < p _c and that P _p {ρ-percolation occurs} > 0 for p > p _c . Here we find lim _{d →∞} d ^1/ρ p _c (ρd, bond) = D ₁ , say. We also find the limit for the analogous quantity for site percolation, that is D ₂ = lim _{d →∞} d ^1/ρ p _c (ρ, d, site). It turns out that for ρ < 1, D ₁ < D ₂ , and neither of these limits equals the analogous limit for the regular d-ary trees. Received: 7 January 1999 / Published online: 14 June 2000     

Brochette percolation

We study bond percolation on the square lattice with one-dimensional inhomogeneities. Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on Z. Select vertical columns at random independently with a given positive probability. Keep (respectively remove) vertical edges in the selected columns, with probability p (respectively 1?p). All horizontal edges and vertical edges lying in unselected columns are kept (respectively removed) with probability q (respectively 1 ? q). We show that, if p > p_c(Z²) (the critical point for homogeneous Bernoulli bond percolation), then q can be taken strictly smaller than p_c(Z²) in such a way that the probability that the origin percolates is still positive.     

A central limit theorem for “critical” first-passage percolation in two dimensions

Summary. Consider (independent) first-passage percolation on the edges of ℤ ² . Denote the passage time of the edge e in ℤ ² by t(e), and assume that P{t(e) = 0} = 1/2, P{0<t(e)<C ₀ } = 0 for some constant C ₀ >0 and that E[t ^δ (e)]<∞ for some δ>4. Denote by b _0,n the passage time from 0 to the halfplane {(x,y): x ≧ n}, and by T( 0 ,nu) the passage time from 0 to the nearest lattice point to nu, for u a unit vector. We prove that there exist constants 0<C ₁ , C ₂ <∞ and γ _n such that C ₁ ( log n) ^1/2 ≦γ _n ≦ C ₂ ( log n) ^1/2 and such that γ _n ⁻¹ [b _0,n −Eb _0,n ] and (√ 2γ _n ) ⁻¹ [T( 0 ,nu) − ET( 0 ,nu)] converge in distribution to a standard normal variable (as n →∞, u fixed). A similar result holds for the site version of first-passage percolation on ℤ ² , when the common distribution of the passage times {t(v)} of the vertices satisfies P{t(v) = 0} = 1−P{t(v) ≧ C ₀ } = p _c (ℤ ² , site ) := critical probability of site percolation on ℤ ² , and E[t ^δ (u)]<∞ for some δ>4. Received: 6 February 1996 / In revised form: 17 July 1996     

The number of infinite clusters in dynamical percolation

Summary. Dynamical percolation is a Markov process on the space of subgraphs of a given graph, that has the usual percolation measure as its stationary distribution. In previous work with O. H?ggstr?m, we found conditions for existence of infinite clusters at exceptional times. Here we show that for ℤ ^d , with p>p _c , a.s. simultaneously for all times there is a unique infinite cluster, and the density of this cluster is θ(p). For dynamical percolation on a general tree Γ, we show that for p>p _c , a.s. there are infinitely many infinite clusters at all times. At the critical value p=p _c , the number of infinite clusters may vary, and exhibits surprisingly rich behaviour. For spherically symmetric trees, we find the Hausdorff dimension of the set T ^k of times where the number of infinite clusters is k, and obtain sharp capacity criteria for a given time set to intersect T ^k . The proof of this capacity criterion is based on a new kernel truncation technique. Received: 5 May 1997 / In revised form: 24 November 1997     

H ∞ -calculus for the Stokes operator on L q -spaces

 It is proved that the Stokes operator on a bounded domain, an exterior domain, or a perturbed half-space Ω admits a bounded H ^∞ -calculus on L _q (Ω) if q(1,∞). Received: 25 January 2002; in final form: 2 October 2002 / Published online: 16 May 2003     

Bootstrap percolation on the hypercube

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2ⁿ sites is occupied with probability p and empty with probability 1−p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c₁,c₂>0 such that for the probability of spanning tends to 1 as n→∞, while for the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function. J. Balogh: work was done while at The University of Memphis, USA Research supported in part by NSF grant DMS0302804 Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900