   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
DOI: https://doi.org/10.1090/S0002-9939-96-03732-X
MathSciNet review: 1371123
Full-text PDF Free Access

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

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

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