Sharp thresholds of graph properties, and the -sat problem |
| |
Authors: | Ehud Friedgut appendix by Jean Bourgain |
| |
Institution: | Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel ; School of Mathematics, Institue of Advanced Study, Princeton, New Jersey 08540 |
| |
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. |
| |
Keywords: | |
|
| 点击此处可从《Journal of the American Mathematical Society》浏览原始摘要信息 |
| 点击此处可从《Journal of the American Mathematical Society》下载免费的PDF全文 |
|