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

DOI:
https://doi.org/10.1090/S0002-9939-96-03732-X

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 denote the Hamming space endowed with the probability measure defined by , where . Let be a monotone subset of . We say that is symmetric if there is a transitive permutation group on such that is invariant under .

**Theorem.** *For every symmetric monotone , if then for . ( is an absolute constant.) *

**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.

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

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

DOI:
https://doi.org/10.1090/S0002-9939-96-03732-X

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