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

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.