Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Every monotone graph property
has a sharp threshold

Authors: Ehud Friedgut and Gil Kalai
Journal: Proc. Amer. Math. Soc. 124 (1996), 2993-3002
MSC (1991): Primary 05C80, 28A35, 60K35
MathSciNet review: 1371123
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let $V_n(p)= \{0,1\}^n$ denote the Hamming space endowed with the probability measure $\mu _p$ defined by $\mu _p (\epsilon _1, \epsilon _2, \dots , \epsilon _n)= p^k \cdot (1-p)^{n-k}$, where $k=\epsilon _1 +\epsilon _2 +\cdots +\epsilon _n$. Let $A$ be a monotone subset of $V_n$. We say that $A$ is symmetric if there is a transitive permutation group $\Gamma $ on $\{1,2,\dots , n\}$ such that $A$ is invariant under $\Gamma $.

Theorem. For every symmetric monotone $A$, if $\mu _p(A)>\epsilon $ then $\mu _q(A)>1-\epsilon $ for $q=p+ c_1 \log (1/2\epsilon )/\log n$. ($c_1$ is an absolute constant.)

References [Enhancements On Off] (What's this?)

  • 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. MR 1140703
  • 2. William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 0385456
  • 3. M. Ben-Or and N. Linial, Collective coin flipping, in Randomness and Computation (S. Micali, ed.), 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. MR 809996
  • 5. B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, 10.1007/BF02579198
  • 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. MR 1194785, 10.1007/BF02808010
  • 7. Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1–22. MR 599634, 10.1112/blms/13.1.1
  • 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). MR 0125031
  • 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). MR 0472604
  • 14. Lucio Russo, On the critical percolation probabilities, Z. Wahrsch. Verw. Gebiete 56 (1981), no. 2, 229–237. MR 618273, 10.1007/BF00535742
  • 15. Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, 10.1007/BF00537230
  • 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. MR 1215783, 10.1007/BF01895691
  • 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.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05C80, 28A35, 60K35

Retrieve articles in all journals with MSC (1991): 05C80, 28A35, 60K35

Additional Information

Ehud Friedgut
Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel

Gil Kalai
Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel and Institute for Advanced Study, Princeton, New Jersey 08540

Received by editor(s): March 27, 1995
Additional Notes: Research supported in part by grants from the Israeli Academy of Sciences, the U.S.-Israel Binational Science Foundation, the Sloan foundation and by a grant from the state of Niedersachsen.
Communicated by: Jeffry N. Kahn
Article copyright: © Copyright 1996 American Mathematical Society