Remote Access Journal of the American Mathematical Society
Green Open Access

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

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

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