zbMATH — the first resource for mathematics

The critical probability for random Voronoi percolation in the plane is 1/2. (English) Zbl 1100.60054
Summary: We study percolation in the following random environment: let \(Z\) be a Poisson process of constant intensity on \(\mathbb R^{2}\), and form the Voronoi tessellation of \(\mathbb R^{2}\) 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 \(\mathbb Z^{2}\).
The result corresponding to Harris’ theorem for bond percolation in \(\mathbb Z^{2}\) 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 \(\mathbb Z^{2}\); we hope they will be applicable in other contexts as well.

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60K37 Processes in random environments
52C99 Discrete geometry
60C05 Combinatorial probability
82B43 Percolation
Full Text: DOI arXiv
[1] Ahlswede, R., Daykin, D.E.: An inequality for the weights of two families of sets, their unions and intersections. Z. Wahrsch. Verw. Gebiete 43, 183–185 (1978) · Zbl 0357.04011 · doi:10.1007/BF00536201
[2] Aizenman, M.: Scaling limit for the incipient spanning clusters, in Mathematics of multiscale materials (Minneapolis, MN, 1995–1996). IMA Vol. Math. Appl. 99, 1–24 (1998) · Zbl 0941.74013
[3] Alexander, K.S.: The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees. Ann. Appl. Probab. 6, 466–494 (1996) · Zbl 0855.60009 · doi:10.1214/aoap/1034968140
[4] Balister, P., Bollobás, B., Quas, A.: Percolation in Voronoi tilings. Random Structures and Algorithms 26, 310–318 (2005) · Zbl 1065.60142 · doi:10.1002/rsa.20043
[5] Balister, P., Bollobás, B., Walters, M.: Continuum percolation with steps in the square or the disc. Random Structures and Algorithms 26, 392–403 (2005) · Zbl 1072.60083 · doi:10.1002/rsa.20064
[6] Benjamini, I., Schramm, O.: Conformal invariance of Voronoi percolation. Comm. Math. Phys. 197, 75–107 (1998) · Zbl 0921.60081 · doi:10.1007/s002200050443
[7] Bollobás, B., Riordan, O.M.: A short proof of the Harris-Kesten Theorem, to appear in Bulletin of the London Math. Soc. Preprint available from http://arXiv.org/ math/0410359
[8] Bollobás, B., Riordan, O.M.: Sharp thresholds and percolation in the plane, to appear in Random Structures and Algorithms. Preprint available from http://arXiv.org/ math/0412510
[9] Bourgain, J., Kahn, J., Kalai, G., Katznelson, Y., Linial, N.: The influence of variables in product spaces. Israel J. Math. 77, 55–64 (1992) · Zbl 0771.60002 · doi:10.1007/BF02808010
[10] Broadbent, S.R., Hammersley, J.M.: Percolation processes. I. Crystals and mazes. Proc. Cambridge Philos. Soc. 53, 629–641 (1957) · Zbl 0091.13901 · doi:10.1017/S0305004100032680
[11] Burton, R.M., Keane, M.: Density and uniqueness in percolation. Comm. Math. Phys. 121, 501–505 (1989) · Zbl 0662.60113 · doi:10.1007/BF01217735
[12] Freedman, M.H.: Percolation on the projective plane. Math. Res. Lett. 4, 889–894 (1997) · Zbl 0902.60085
[13] Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124, 2993–3002 (1996) · Zbl 0864.05078 · doi:10.1090/S0002-9939-96-03732-X
[14] Grimmett, G.: Percolation. Second edition. Springer-Verlag, Berlin, xiv+444 pp. ISBN 3-540-64902-6, 1999 · Zbl 0926.60004
[15] Hammersley, J.M.: Percolation processes. II. The connective constant. Proc. Cambridge Philos. Soc. 53, 642–645 (1957) · Zbl 0091.13902
[16] Hammersley, J.M.: Percolation processes: Lower bounds for the critical probability. Ann. Math. Statist. 28, 790–795 (1957) · Zbl 0091.13903 · doi:10.1214/aoms/1177706894
[17] Hammersley, J.M.: Bornes supérieures de la probabilité critique dans un processus de filtration, Le calcul des probabilités et ses applications. Paris, 15–20 juillet 1958, Colloques Internationaux du Centre National de la Recherche Scientifique, LXXXVII , pp. 17–37 (1959)
[18] Harris, T.E.: A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56, 13–20 (1960) · Zbl 0122.36403 · doi:10.1017/S0305004100034241
[19] Kahn, J., Kalai, G., Linial, N.: The influence of variables on boolean functions. Proc. 29-th Annual Symposium on Foundations of Computer Science, pp. 68–80, Computer Society Press, 1988
[20] Kesten, H.: The critical probability of bond percolation on the square lattice equals 1/2. Comm. Math. Phys. 74, 41–59 (1980) · Zbl 0441.60010 · doi:10.1007/BF01197577
[21] Kleitman, D.J.: Families of non-disjoint subsets. J. Combinatorial Theory 1, 153–155 (1966) · Zbl 0141.00801 · doi:10.1016/S0021-9800(66)80012-1
[22] Langlands, R., Pouliot, P., Saint-Aubin, Y.: Conformal invariance in two-dimensional percolation, Bull. Amer. Math. Soc. 30, 1–61 (1994) · Zbl 0794.60109 · doi:10.1090/S0273-0979-1994-00456-2
[23] Liggett, T.M., Schonmann, R.H., Stacey, A.M.: Domination by product measures. Annals of Probability 25, 71–95 (1997) · Zbl 0882.60046 · doi:10.1214/aop/1024404279
[24] Russo, L.: A note on percolation. Z. Wahrsch. Verw. Gebiete 43, 39–48 (1978) · Zbl 0363.60120 · doi:10.1007/BF00535274
[25] Seymour, P.D., Welsh, D.J.A.: Percolation probabilities on the square lattice, in Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). Ann. Discrete Math. 3, 227–245 (1978) · Zbl 0405.60015
[26] Smirnov, S.: Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, Comptes Rendus de l’Académie des Sciences. Série I. Mathématique, 333, 239–244 (2001). Expanded version available at http://www.math.kth.se/\(\sim\)stas/ papers · Zbl 0985.60090
[27] Vahidi-Asl, M.Q., Wierman, J.C.: First-passage percolation on the Voronoi tessellation and Delaunay triangulation. in Random graphs ’87 (Poznań, 1987), Wiley, Chichester, pp. 341–359, 1990 · Zbl 0760.05023
[28] Vahidi-Asl, M.Q., Wierman, J.C.: A shape result for first-passage percolation on the Voronoi tessellation and Delaunay triangulation, in Random graphs, Vol. 2 (Poznań, 1989), Wiley-Intersci. Publ., Wiley, New York, pp. 247–262, 1992 · Zbl 0816.60099
[29] Vahidi-Asl, M.Q., Wierman, J.C.: Upper and lower bounds for the route length of first-passage percolation in Voronoi tessellations. Bull. Iranian Math. Soc. 19, 15–28 (1993) · Zbl 0802.60096
[30] A. Zvavitch, The critical probability for Voronoi percolation, MSc. thesis, Weizmann Institute of Science, 1996
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.