Sharp thresholds of graph properties, and the 𝑘-sat problem
E Friedgut, J Bourgain - Journal of the American mathematical Society, 1999 - ams.org
E Friedgut, J Bourgain
Journal of the American mathematical Society, 1999•ams.orgGiven 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 …
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 …
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 . As an application of the main theorem we settle the question of the existence of a sharp threshold for the satisfiability of a random -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
ams.org
以上显示的是最相近的搜索结果。 查看全部搜索结果