Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

Sharp thresholds of graph properties,
and the $k$-sat problem


Authors: Ehud Friedgut and appendix by Jean Bourgain
Journal: J. Amer. Math. Soc. 12 (1999), 1017-1054
MSC (1991): Primary 05C80, 28A35
Published electronically: May 27, 1999
MathSciNet review: 1678031
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given a monotone graph property $P$, consider $\mu _p(P)$, the probability that a random graph with edge probability $p$ will have $P$. The function $d\mu _p(P)/dp$ is the key to understanding the threshold behavior of the property $P$. We show that if $d\mu _p(P)/dp$ is small (corresponding to a non-sharp threshold), then there is a list of graphs of bounded size such that $P$ can be approximated by the property of having one of the graphs as a subgraph. One striking consequence of this result is that a coarse threshold for a random graph property can only happen when the value of the critical edge probability is a rational power of $n$.

As an application of the main theorem we settle the question of the existence of a sharp threshold for the satisfiability of a random $k$-CNF formula.

An appendix by Jean Bourgain was added after the first version of this paper was written. In this appendix some of the conjectures raised in this paper are proven, along with more general results.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (1991): 05C80, 28A35

Retrieve articles in all journals with MSC (1991): 05C80, 28A35


Additional Information

Ehud Friedgut
Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel
Email: ehudf@math.huji.ac.il

appendix by Jean Bourgain
Affiliation: School of Mathematics, Institue of Advanced Study, Princeton, New Jersey 08540

DOI: http://dx.doi.org/10.1090/S0894-0347-99-00305-7
PII: S 0894-0347(99)00305-7
Received by editor(s): May 2, 1997
Received by editor(s) in revised form: July 14, 1998
Published electronically: May 27, 1999
Additional Notes: This paper is part of a Ph.D. thesis prepared under the supervision of Prof. Gil Kalai.
Article copyright: © Copyright 1999 American Mathematical Society