Stochastic domination and comb percolation

Alexander E Holroyd (Microsoft Research)
James B Martin (University of Oxford)


There exists a Lipschitz embedding of a d-dimensional comb graph (consisting of infinitely many parallel copies of $\mathbb{Z}^{d-1}$ joined by a perpendicular copy) into the open set of site percolation on $\mathbb{Z}^d$, whenever the parameter p is close enough to 1 or the Lipschitz constant is sufficiently large. This is proved using several new results and techniques involving stochastic domination, in contexts that include a process of independent overlapping intervals on $\mathbb{Z}$, and first-passage percolation on general graphs.

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

Pages: 1-16

Publication Date: January 8, 2014

DOI: 10.1214/EJP.v19-2806


  • Baccelli, Francois; Foss, Sergey. Poisson hail on a hot ground. J. Appl. Probab. 48A (2011), New frontiers in applied probability: a Festschrift for Soren Asmussen, 343--366. ISBN: 0-902016-08-3 MR2865637
  • R. Basu and A. Sly, Lipschitz embeddings of random sequences, 2012, arXiv:1204.2931.
  • Dirr, N.; Dondl, P. W.; Grimmett, G. R.; Holroyd, A. E.; Scheutzow, M. Lipschitz percolation. Electron. Commun. Probab. 15 (2010), 14--21. MR2581044
  • Dirr, Nicolas; Dondl, Patrick W.; Scheutzow, Michael. Pinning of interfaces in random media. Interfaces Free Bound. 13 (2011), no. 3, 411--421. MR2846018
  • Fontes, Luiz; Newman, Charles M. First passage percolation for random colorings of ${\bf Z}^ d$. Ann. Appl. Probab. 3 (1993), no. 3, 746--762. MR1233623
  • Grimmett, Geoffrey. Percolation. Second edition. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 321. Springer-Verlag, Berlin, 1999. xiv+444 pp. ISBN: 3-540-64902-6 MR1707339
  • Grimmett, Geoffrey. Three problems for the clairvoyant demon. Probability and mathematical genetics, 380--396, London Math. Soc. Lecture Note Ser., 378, Cambridge Univ. Press, Cambridge, 2010. MR2744248
  • Grimmett, Geoffrey R.; Holroyd, Alexander E. Plaquettes, spheres, and entanglement. Electron. J. Probab. 15 (2010), 1415--1428. MR2721052
  • Grimmett, G. R.; Holroyd, A. E. Geometry of Lipschitz percolation. Ann. Inst. Henri PoincarĂ© Probab. Stat. 48 (2012), no. 2, 309--326. MR2954256
  • Grimmett, Geoffrey R.; Holroyd, Alexander E. Lattice embeddings in percolation. Ann. Probab. 40 (2012), no. 1, 146--161. MR2917770
  • Liggett, Thomas M. Interacting particle systems. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 276. Springer-Verlag, New York, 1985. xv+488 pp. ISBN: 0-387-96069-4 MR0776231
  • Liggett, T. M.; Schonmann, R. H.; Stacey, A. M. Domination by product measures. Ann. Probab. 25 (1997), no. 1, 71--95. MR1428500
  • Lyons, Russell. Phase transitions on nonamenable graphs. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. J. Math. Phys. 41 (2000), no. 3, 1099--1126. MR1757952
  • Russo, Lucio. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129--139. MR0671248
  • Zerner, Martin P. W. Interpolation percolation. Electron. J. Probab. 16 (2011), no. 33, 981--1000. MR2801458

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