Percolation of Arbitrary words on the Close-Packed Graph of $\mathbb{Z}^2$

Harry Kesten (Cornell University)
Vladas Sidoravicius (IMPA)
Yu Zhang (University of Colorado)


Let ${\Bbb Z}^2_{cp}$ be the close-packed graph of $\Bbb Z^2$, that is, the graph obtained by adding to each face of $\Bbb Z^2$ its diagonal edges. We consider site percolation on $\Bbb Z^2_{cp}$, namely, for each $v$ we choose $X(v) = 1$ or 0 with probability $p$ or $1-p$, respectively, independently for all vertices $v$ of $\Bbb Z^2_{cp}$. We say that a word $(\xi_1, \xi_2,\dots) \in \{0,1\}^{\Bbb N}$ is seen in the percolation configuration if there exists a selfavoiding path $(v_1, v_2, \dots)$ on $\Bbb Z^2_{cp}$ with $X(v_i) = \xi_i, i \ge 1$. $p_c(\Bbb Z^2, \text{site})$ denotes the critical probability for site-percolation on $\Bbb Z^2$. We prove that for each fixed $p \in \big (1- p_c(\Bbb Z^2, \text{site}), p_c(\Bbb Z^2, \text{site})\big )$, with probability 1 all words are seen. We also show that for some constants $C_i > 0$ there is a probability of at least $C_1$ that all words of length $C_0n^2$ are seen along a path which starts at a neighbor of the origin and is contained in the square $[-n,n]^2$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-27

Publication Date: February 12, 2001

DOI: 10.1214/EJP.v6-77


  1. Benjamini, I. and Kesten, H. (1995), Percolation of arbitrary words in {0,1}N. Ann. Probab. 23, 1024-1060. Math. Review 97a:60140
  2. van den Berg, J. and Ermakov, A. (1996), A new lower bound for the critical probability of site percolation on the square lattice. Random Structures and Algorithms 8, 199-212. Math. Review 99b:60165
  3. Grimmett, G. R. (1999), Percolation. 2nd ed., Springer Verlag, Berlin. Math. Review 2001a:60114
  4. Harris, T. E. (1960), A lower bound for the critical probability in a certain percolation process. Proc. Cambr. Phil. Soc. 56, 13-20. Math. Review 22:6023
  5. Kesten, H. (1982), Percolation Theory for Mathematicians. Birkhauser-Boston. Math. Review 84i:60145
  6. Kesten, H., Sidoravicius, V. and Zhang, Y. (1998), Almost all words are seen in critical site percolation on the triangular lattice. Elec. J. Probab. 3, 1-75. Math. Review 94a:60134
  7. Newman, M. H. A. (1951), Elements of the Topology of Plane Sets of Points. 2nd ed., Cambr. Univ. Press. Math. Review 82i:60182
  8. Smythe, R. T. and Wierman, J. C. (1978), Percolation on the Square Lattice. Lecture Notes in Mathematics, vol 671, Springer-Verlag. Math. Review 80a:60135

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.