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

Authors:
Open Access
Publisher website
Google Scholar
Abstract
Given a monotone graph property , consider , the probability that a random graph with edge probability will have . The function is the key to understanding the threshold behavior of the property . We show that if is small (corresponding to a non-sharp threshold), then there is a list of graphs of bounded size such that 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 .

This publication has 11 references indexed in Scilit: