zbMATH — the first resource for mathematics

Noise sensitivity in continuum percolation. (English) Zbl 1305.60100
Authors’ abstract: We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first which involves a percolation model with critical probability \(p_c = 1/2\). Our proof uses a version of the Benjamini-Kalai-Schramm theorem for biased product measures. A quantitative version of this result was recently proved by N. Keller and G. Kindler [Combinatorica 33, No. 1, 45–71 (2013; Zbl 1299.05308)]. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with pc bounded away from zero; this method is based on an extremal result for non-uniform hypergraphs.
Reviewer’s remark: The reading of this advanced contribution presupposes a profound knowledge of the contents of the monographs [N. Alon and J. H. Spencer, The probabilistic method. With an appendix on the life and work of Paul Erdős. 3rd ed. Hoboken, NJ: John Wiley & Sons (2008; Zbl 1148.05001); B. Bollobas and O. Riordan, Percolation. Cambridge: Cambridge University Press (2006; Zbl 1118.60001); G. Grimmett, Percolation. 2nd ed. Berlin: Springer (1999; Zbl 0926.60004); R. Meester and R. Roy, Continuum percolation. Cambridge: Cambridge Univ. Press (1996; Zbl 0858.60092)].

60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI arXiv
[1] Aharoni, R., A problem in rearrangements of (0,1) matrices, Discrete Mathematics, 30, 191-201, (1980) · Zbl 0468.05017
[2] D. Ahlberg, Partially observed Boolean sequences and noise sensitivity, Combinatorics, Probability and Computing, to appear. · Zbl 1326.60012
[3] Ahlswede, R.; Katona, G. O. H., Graphs with maximal number of adjacent pairs of edges, Acta Mathematica Academiae Scientiarum Hungaricae, 32, 97-120, (1978) · Zbl 0386.05036
[4] Alexander, K. S., The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees, The Annals of Applied Probability, 6, 466-494, (1996) · Zbl 0855.60009
[5] N. Alon and J. Spencer, The Probabilistic Method, 3rd edition, Wiley Interscience, New York, 2008. · Zbl 1148.05001
[6] Balister, P.; Bollobás, B.; Walters, M., Continuum percolation with steps in the square or the disc, Random Structures & Algorithms, 26, 392-403, (2005) · Zbl 1072.60083
[7] Benjamini, I.; Schramm, O., Conformal invariance of Voronoi percolation, Communications in Mathematical Physics, 197, 75-107, (1996) · Zbl 0921.60081
[8] Benjamini, I.; Schramm, O., Exceptional planes of percolation, Probability Theory and Related Fields, 111, 551-564, (1998) · Zbl 0910.60076
[9] Benjamini, I.; Kalai, G.; Schramm, O., Noise sensitivity of Boolean functions and applications to percolation, Institut des Hautes Études Scientifiques. Publications Mathématiques, 90, 5-43, (1999) · Zbl 0986.60002
[10] Benjamini, I.; Schramm, O.; Wilson, D. B., Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be Read, 244-250, (2005), New York · Zbl 1192.68851
[11] Bey, C., An upper bound on the sum of squares of degrees in a hypergraph, Discrete Mathematics, 269, 259-263, (2003) · Zbl 1024.05043
[12] B. Bollobás, Modern Graph Theory, 2nd edition, Springer, Berlin, 2002.
[13] Bollobás, B.; Riordan, O., The critical probability for random Voronoi percolation in the plane is 1/2, Probability Theory and Related Fields, 136, 417-468, (2006) · Zbl 1100.60054
[14] B. Bollobás and O. Riordan, Percolation, Cambridge University Press, Cambridge, 2006. · Zbl 1118.60001
[15] Bourgain, J.; Kahn, J.; Kalai, G.; Katznelson, Y.; Linial, N., The influence of variables in product spaces, Israel Journal of Mathematics, 77, 55-64, (1992) · Zbl 0771.60002
[16] Broman, E. I.; Garban, C.; Steif, J. E., Exclusion sensitivity of Boolean functions, Probability Theory and Related Fields, 155, 621-663, (2013) · Zbl 1280.60055
[17] Caen, D., An upper bound on the sum of squares of degrees in a graph, Discrete Mathematics, 185, 245-248, (1998) · Zbl 0955.05059
[18] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics, 23, 493-507, (1952) · Zbl 0048.11804
[19] Friedgut, E., Influences in product spaces: KKL and BKKKL revisited, Combinatorics, Probability and Computing, 13, 17-29, (2004) · Zbl 1057.60007
[20] Garban, C., Oded schramm’s contributions to noise sensitivity, The Annals of Probability, 39, 1702-1767, (2011) · Zbl 1252.82090
[21] Garban, C.; Pete, G.; Schramm, O., The Fourier spectrum of critical percolation, Acta Mathematica, 205, 19-104, (2010) · Zbl 1219.60084
[22] Gilbert, E. N., Random plane networks, Journal of the Society for Industrial and Applied Mathematics, 9, 533-543, (1961) · Zbl 0112.09403
[23] G. Grimmett, Percolation, 2nd edition, Springer-Verlag, Berlin, 1999. · Zbl 0926.60004
[24] Häggström, O.; Peres, Y.; Steif, J. E., Dynamical percolation, Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, 33, 497-528, (1997) · Zbl 0894.60098
[25] A. Hammond, G. Pete and O. Schramm, Local time on the exceptional set of dynamical percolation, and the incipient infinite cluster, submitted, arXiv:1208.3826. · Zbl 1341.60128
[26] J. Kahn, G. Kalai and N. Linial, The influence of variables on Boolean functions, in 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 68-80. · Zbl 1219.60084
[27] Keller, N., A simple reduction from a biased measure on the discrete cube to the uniform measure, European Journal of Combinatorics, 33, 1943-1957, (2012) · Zbl 1248.28005
[28] Keller, N.; Kindler, G., Quantitative relation between noise sensitivity and influences, Combinatorica, 33, 45-71, (2013) · Zbl 1299.05308
[29] Keller, N.; Mossel, E.; Schlank, T., A note on the entropy/influence conjecture, Discrete Mathematics, 312, 3364-3372, (2012) · Zbl 1252.05200
[30] R. Meester and R. Roy, Continuum Percolation, Cambridge University Press, Cambridge, 1996. · Zbl 0858.60092
[31] Menshikov, M. V.; Sidorenko, A. F., Coincidence of critical points in Poisson percolation models, Rossiıskaya Akademiya Nauk. Teoriya Veroyatnosteı i ee Primeneniya, 32, 603-606, (1987)
[32] R. O’Donnell, Computational applications of noise sensitivity, Ph.D, thesis, MIT, 2003. · Zbl 1024.05043
[33] Paley, R. E. A. C., A remarkable series of orthogonal functions, Proceedings of the London Mathematical Society, 34, 241, (1932) · JFM 58.0284.03
[34] Roy, R., The Russo-seymour-welsh theorem and the equality of critical densities and the dual critical densities for continuum percolation, The Annals of Probability, 18, 1563-1575, (1990) · Zbl 0719.60119
[35] Schramm, O.; Steif, J., Quantitative noise sensitivity and exceptional times for percolation, Annals of Mathematics, 171, 619-672, (2010) · Zbl 1213.60160
[36] Steif, J., A survey of dynamical percolation, No. 61, 145-174, (2009), Basel · Zbl 1186.60106
[37] Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Institut des Hautes Études Scientifiques. Publications Mathématiques, 81, 73-205, (1995) · Zbl 0864.60013
[38] Walsh, J. L., A closed set of normal orthogonal functions, American Journal of Mathematics, 45, 5-24, (1923) · JFM 49.0293.03
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.