Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
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 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 $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?)


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
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: http://dx.doi.org/10.1090/S0002-9939-96-03732-X
PII: S 0002-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