zbMATH — the first resource for mathematics

Every monotone graph property has a sharp threshold. (English) Zbl 0864.05078
This paper proves a conjecture of Linial about random graphs: every monotone graph property has a sharp threshold. The authors show this to be a special case of a more general result. To describe the general result, consider all \(n\)-dimensional 0-1 vectors. Endow a measure \(\mu_p\) on this set by setting each element of the vector to 1 with probability \(p\) independently of the other elements. Consider any monotone set \(A\) of 0-1 vectors such that \(\mu_p(A)>\varepsilon\). If there is a transitive permutation group on \(\{1,2,\dots,n\}\) that leaves \(A\) invariant then \(\mu_q(A)>1-\varepsilon\) where \(q=p+c\log(1/2\varepsilon)/(\log n)\). Here \(c\) is an absolute constant.
The paper describes some extensions of this result as well as applications to problems other than the one raised by Linial. Of particular interest is the connection to Talagrands work on isoperimetric inequalities.

05C80 Random graphs (graph-theoretic aspects)
28A35 Measures and integrals in product spaces
60K35 Interacting random processes; statistical mechanics type models; percolation theory
Full Text: DOI
[1] Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. · Zbl 0767.05001
[2] William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159 – 182. · Zbl 0338.42017 · doi:10.2307/1970980 · doi.org
[3] M. Ben-Or and N. Linial, Collective coin flipping, in Randomness and Computation , Academic Press, New York, 1990, pp. 91-115. Earlier version: Collective coin flipping, robust voting games, and minima of Banzhaf value, Proc. 26th IEEE Symp. on the Foundation of Computer Science, 1985, pp. 408-416.
[4] Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. · Zbl 0567.05042
[5] B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35 – 38. · Zbl 0648.05048 · doi:10.1007/BF02579198 · doi.org
[6] Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), no. 1-2, 55 – 64. · Zbl 0771.60002 · doi:10.1007/BF02808010 · doi.org
[7] Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1 – 22. · Zbl 0463.20003 · doi:10.1112/blms/13.1.1 · doi.org
[8] P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17 – 61 (English, with Russian summary). · Zbl 0103.16301
[9] G. Grimmet, Percolation, Springer-Verlag, New York, 1989.
[10] J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., 68-80, Computer Society Press, 1988.
[11] J. Håstad (1988), Almost optimal lower bounds for small depth circuits, in S. Micali, ed., Advances in Computer Research, Vol. 5 :Randomness and Computation, 143-170, JAI Press, Greenwich, CT, 1988.
[12] N. Linial, private communication.
[13] G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101 – 108 (Russian). · Zbl 0322.05147
[14] Lucio Russo, On the critical percolation probabilities, Z. Wahrsch. Verw. Gebiete 56 (1981), no. 2, 229 – 237. · Zbl 0457.60084 · doi:10.1007/BF00535742 · doi.org
[15] Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129 – 139. · Zbl 0501.60043 · doi:10.1007/BF00537230 · doi.org
[16] M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem, Geom. Funct. Anal. 3 (1993), no. 3, 295 – 314. · Zbl 0806.46035 · doi:10.1007/BF01895691 · doi.org
[17] M. Talagrand, On Russo’s approximate zero-one law, Ann. of Probab. 22(1994), 1576-1587. CMP 95:04
[18] M. Talagrand, On boundaries and influences, Combinatorica, to appear.
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.