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


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?)

  • 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
  • William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 385456, DOI
  • 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.
  • Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
  • B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI
  • 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, DOI
  • Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1–22. MR 599634, DOI
  • 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 125031
  • G. Grimmet, Percolation, Springer-Verlag, New York, 1989.
  • 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.
  • 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.
  • N. Linial, private communication.
  • G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
  • Lucio Russo, On the critical percolation probabilities, Z. Wahrsch. Verw. Gebiete 56 (1981), no. 2, 229–237. MR 618273, DOI
  • Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI
  • 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, DOI
  • M. Talagrand, On Russo’s approximate zero-one law, Ann. of Probab. 22(1994), 1576-1587.
  • 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
MR Author ID: 195990

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