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 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 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. 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 385456, https://doi.org/10.2307/1970980
- 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, https://doi.org/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, https://doi.org/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, https://doi.org/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, https://doi.org/10.1007/BF00535742
- 15. Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, https://doi.org/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, https://doi.org/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.
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