×

zbMATH — the first resource for mathematics

Noise sensitivity and Voronoi percolation. (English) Zbl 1402.60122
Summary: In this paper we study noise sensitivity and threshold phenomena for Poisson Voronoi percolation on \(\mathbb{R}^2\). In the setting of Boolean functions, both threshold phenomena and noise sensitivity can be understood via the study of randomized algorithms. Together with a simple discretization argument, such techniques apply also to the continuum setting. Via the study of a suitable algorithm we show that box-crossing events in Voronoi percolation are noise sensitive and present a threshold phenomenon with polynomial window. We also study the effect of other kinds of perturbations, and emphasize the fact that the techniques we use apply for a broad range of models.

MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Daniel Ahlberg, Erik Broman, Simon Griffiths, and Robert Morris. Noise sensitivity in continuum percolation. Israel Journal of Mathematics, 201(2):847–899, 2014. · Zbl 1305.60100
[2] Daniel Ahlberg, Simon Griffiths, Robert Morris, and Vincent Tassion. Quenched Voronoi percolation. Advances in Mathematics, 286:889–911, 2016. · Zbl 1335.60178
[3] Daniel Ahlberg, and Jeffrey E Steif. Scaling limits for the threshold window: When does a monotone boolean function flip its outcome? In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, volume 53, pages 2135–2161. Institut Henri Poincaré, 2017. · Zbl 1412.60052
[4] Daniel Ahlberg, Vincent Tassion, and Augusto Teixeira. Sharpness of the phase transition for continuum percolation in \(\mathbb{R} ^{2}\). Probability Theory and Related Fields, 172(1-2):525–581, 2018. · Zbl 1401.60173
[5] Itai Benjamini, Gil Kalai, and Oded Schramm. Noise sensitivity of Boolean functions and applications to percolation. Publications Mathématiques de l’Institut des Hautes Études Scientifiques, 90(1):5–43, 1999. · Zbl 0986.60002
[6] Itai Benjamini and Oded Schramm. Conformal invariance of Voronoi percolation. Comm. Math. Phys., 197(1):75–107, 1998. · Zbl 0921.60081
[7] Béla Bollobás and Oliver Riordan. The critical probability for random Voronoi percolation in the plane is 1/2. Probability theory and related fields, 136(3):417–468, 2006. · Zbl 1100.60054
[8] Erik I Broman, Christophe Garban, and Jeffrey E Steif. Exclusion sensitivity of Boolean functions. Probability theory and related fields, 155(3-4):621–663, 2013. · Zbl 1280.60055
[9] Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion. Exponential decay of connection probabilities for subcritical voronoi percolation in \(\mathbb{R} ^{d}\). Probability Theory and Related Fields, pages 1–12, 2017. · Zbl 1395.82043
[10] Hugo Duminil-Copin, Aran Raoufi, and Vincent Tassion. Sharp phase transition for the random-cluster and Potts models via decision trees. Preprint, see arXiv:1705.03104. · Zbl 1395.82043
[11] Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
[12] Ehud Friedgut and Gil Kalai. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, 124(10):2993–3002, 1996. · Zbl 0864.05078
[13] Christophe Garban, Gábor Pete, and Oded Schramm. The Fourier spectrum of critical percolation. Acta Mathematica, 205(1):19–104, 2010. · Zbl 1219.60084
[14] Christophe Garban and Jeffrey E Steif. Noise sensitivity of Boolean functions and percolation, volume 5. Cambridge University Press, 2014. · Zbl 1355.06001
[15] Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions. In Foundations of Computer Science, 1988., 29th Annual Symposium on, pages 68–80. IEEE, 1988.
[16] Harry Kesten. The critical probability of bond percolation on the square lattice equals \(1\over 2\). Comm. Math. Phys., 74(1):41–59, 1980. · Zbl 0441.60010
[17] Ryan O’Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.
[18] Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A Servedio. Every decision tree has an influential variable. In Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, pages 31–39. IEEE, 2005.
[19] Ryan O’Donnell and Rocco A Servedio. Learning monotone decision trees in polynomial time. SIAM Journal on Computing, 37(3):827–844, 2007. · Zbl 1147.68028
[20] Lucio Russo. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete, 61(1):129–139, 1982. · Zbl 0501.60043
[21] Oded Schramm and Jeffrey E. Steif. Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2), 171(2):619–672, 2010. · Zbl 1213.60160
[22] Michel Talagrand. On Russo’s approximate zero-one law. The Annals of Probability, pages 1576–1587, 1994. · Zbl 0819.28002
[23] Vincent Tassion. Crossing probabilities for Voronoi percolation. Ann. Probab., 44(5):3385–3398, 2016. · Zbl 1352.60130
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.