## Every monotone graph property has a sharp threshold

HTML articles powered by AMS MathViewer

- by Ehud Friedgut and Gil Kalai PDF
- Proc. Amer. Math. Soc.
**124**(1996), 2993-3002 Request permission

## 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

- 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 10.2307/1970980 - 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 10.1007/BF02579198 - 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 10.1007/BF02808010 - Peter J. Cameron,
*Finite permutation groups and finite simple groups*, Bull. London Math. Soc.**13**(1981), no. 1, 1–22. MR**599634**, DOI 10.1112/blms/13.1.1 - 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 10.1007/BF00535742 - Lucio Russo,
*An approximate zero-one law*, Z. Wahrsch. Verw. Gebiete**61**(1982), no. 1, 129–139. MR**671248**, DOI 10.1007/BF00537230 - 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 10.1007/BF01895691 - 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.

## Additional Information

**Ehud Friedgut**- Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel
- Email: ehudf@math.huji.ac.il
**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
- © Copyright 1996 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**124**(1996), 2993-3002 - MSC (1991): Primary 05C80, 28A35, 60K35
- DOI: https://doi.org/10.1090/S0002-9939-96-03732-X
- MathSciNet review: 1371123