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

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?)

  • 1. D. Achlioptas, E. Friedgut, A Threshold for $k$-Colorability, Random Structures and Algorithms 14 (1999) 63-70. CMP 99:05
  • 2. R. Aharoni, N. Linial, Minimal Non-2-colorable Hypergraphs and Minimal Unsatisfiable Formulas, Journal of Combinatorial Theory, Series A Vol. 43 no.2 November 1986. MR 88b:05059
  • 3. N. Alon and R. Yuster, Threshold functions for $H$-factors, Combinatorics, Probability and Computing 2 (1993), 137-144. MR 94k:05149
  • 4. J. van den Berg and H. Kesten, Inequalities with application to percolation and reliability, Journal of Applied Probability 22 (1985) 556-569. MR 87b:60027
  • 5. B. Bollobás, Random Graphs, Academic Press, London, 1985. MR 87f:05152
  • 6. B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1986) 35-38. MR 88g:05122
  • 7. J. Bourgain, G. Kalai, Influence of variables in product spaces under group symmetries, to appear in GAFA.
  • 8. A.Z. Broder, A. M. Frieze, E. Upfal (1993), On the Satisfiability and Maximum Satisfiability of Random 3-CNF Formulas. In Proc. 4th. Ann. ACM-SIAM Symposium on Discrete Algorithms, pp322-330. MR 94b:03023
  • 9. M. T. Chao, J. Franco (1986), Probabilistic Analysis of Two Heuristics for the 3-sat. Problem. Siam J. Comput. 15(4). MR 88b:68079
  • 10. V. Chvatal, B. Reed, Mick gets some. Proc. 33rd Ann. FOCS Symp.(1992) 620-627.
  • 11. A. El Maftouhi, W. Fernandez de la Vega, On Random 3-sat, Combinatorics, Probability and Computing (1995) 4, 189-195. MR 96f:03007
  • 12. P. Erdös, A. Rényi, On the evolution of random graphs, Mat Kutató Int. Közl. (1960)5, 17-60. MR 23:A2338
  • 13. E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998) 27-35. CMP 99:02
  • 14. E. Friedgut, G. Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), pp. 1017-1054. MR 97e:05172
  • 15. A. Frieze, S. Janson, Perfect Matchings in Random $s$-uniform Hypergraphs. Random Structures and Algorithms, 7 (1995), no. 1, 41-57. MR 96f:05173
  • 16. A. Frieze, S. Suen, (1992) Analysis of Two Simple Heuristics on a Random Instance of k-sat. Journal of Algorithms 20, (1996) 312-355. MR 97c:68062
  • 17. A. Goerdt (1992) A threshold for satisfiability. In Math. Foundations of Computer Science (I.M.Havel and V.Koubek eds.) Prague, Poland.
  • 18. J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., 68-80, Computer Society Press, 1988.
  • 19. A. Kamath, R. Motwani, K.Palem, P.Spirakis Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. Proc. 35th FOCS pp. 592-603.
  • 20. S. Kirkpatrick, B. Selman, Critical Behaviour in the Satisfiability of Random Boolean Expressions, Science, Vol.264 (1994) 1297-1301. MR 96e:68063
  • 21. M. Kirouris, E. Kranakis and D. Krizanc, Approximating the unsatisfiability threshold of random formulas, in: Algorithms - ESA' 96, Lecture Notes in Computer Science 1136
  • 22. T. Larrabee, Y. Tsuji (1992), Evidence for a Satisfiability Threshold for Random 3CNF Formulas. Technical report UCSC-CRL-92-42, University of California, Santa Cruz.
  • 23. G. Margulis, Probabilistic characteristics of graphs with large connectivity, Prob. Peredachi Inform. 10(1974), 101-108. MR 57:12300
  • 24. D. Reimer, Butterflies, 1995 (to appear).
  • 25. L. Russo, On the critical percolation probabilities, Z. Wahrsch. werw. Gebiete, 43(1978), 39-48.
  • 26. L. Russo, An approximate zero-one law, Z. Wahrsch. werw. Gebiete, 61 (1982), 129-139. MR 84e:60153
  • 27. J. Schmidt-Pruzan, E. Shamir, A threshold for perfect matchings in random $d-$pure hypergraphs, Combinatorica 5 (1985) 81-94.
  • 28. M. Talagrand, On Russo's approximate 0-1 law, The Annals of Probability, 1994, Vol.22 No.3 1576-1587. MR 96g:28009

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