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

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. N. Alon and J. Spencer, The Probabilistic Method, Wiley, New York, 1992. MR 93h:60002
  • 2. W. Beckner, Inequalities in Fourier analysis, Ann. Math. 102 (1975), 159-182. MR 52:6317
  • 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. Bollobás, Random Graphs, Academic Press, London, 1985. MR 87f:05152
  • 5. B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1986) 35-38. MR 88g:05122
  • 6. J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson and N. Linial, The influence of variables in product spaces, Israel J. Math. 77(1992), 55-64. MR 94g:05091
  • 7. P. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13(1981), 1-22. MR 83m:20008
  • 8. P. Erdös and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17-61. MR 23:A2338
  • 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. Margulis, Probabilistic characteristics of graphs with large connectivity, Prob. Peredachi Inform. 10 (1974), no. 2, 101-108; English transl., Problems of Information Transmission 10 (1974), 174--179. MR 57:12300
  • 14. L. Russo, On the critical percolation probabilities, Z. Wahrsch. Verw. Gebiete, 43(1978), 39-48. MR 82i:60182
  • 15. L. Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete, 61 (1982), 129-139. MR 84e:60153
  • 16. M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube and Margulis' graph connectivity theorem, Geometric and Func. Anal. 3(1993), 296-314. MR 94m:26026
  • 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

American Mathematical Society