Sharp thresholds of graph properties, and the 𝑘-sat problem

Friedgut, Ehud; Jean Bourgain, appendix by

doi:10.1090/S0894-0347-99-00305-7

Sharp thresholds of graph properties,
and the -sat problem

Authors: Ehud Friedgut and appendix by Jean Bourgain
Journal: J. Amer. Math. Soc. 12 (1999), 1017-1054
MSC (1991): Primary 05C80, 28A35
DOI: https://doi.org/10.1090/S0894-0347-99-00305-7
Published electronically: May 27, 1999
MathSciNet review: 1678031
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given a monotone graph property , consider $\mu _p(P)$ , the probability that a random graph with edge probability will have . The function $d\mu _p(P)/dp$ is the key to understanding the threshold behavior of the property . 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 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.

1. D. Achlioptas, E. Friedgut, A Threshold for $k$ -Colorability, Random Structures and Algorithms 14 (1999) 63-70. CMP 99:05
2. Ron Aharoni and Nathan Linial, Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas, J. Combin. Theory Ser. A 43 (1986), no. 2, 196–204. MR 867645, https://doi.org/10.1016/0097-3165(86)90060-9
3. Noga Alon and Raphael Yuster, Threshold functions for 𝐻-factors, Combin. Probab. Comput. 2 (1993), no. 2, 137–144. MR 1249126, https://doi.org/10.1017/S0963548300000559
4. J. van den Berg and H. Kesten, Inequalities with applications to percolation and reliability, J. Appl. Probab. 22 (1985), no. 3, 556–569. MR 799280, https://doi.org/10.1017/s0021900200029326
5. Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
6. B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, https://doi.org/10.1007/BF02579198
7. J. Bourgain, G. Kalai, Influence of variables in product spaces under group symmetries, to appear in GAFA.
8. Andrei Z. Broder, Alan M. Frieze, and Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Austin, TX, 1993) ACM, New York, 1993, pp. 322–330. MR 1213244
9. Ming-Te Chao and John Franco, Probabilistic analysis of two heuristics for the 3-satisfiability problem, SIAM J. Comput. 15 (1986), no. 4, 1106–1118. MR 861375, https://doi.org/10.1137/0215080
10. V. Chvatal, B. Reed, Mick gets some. Proc. 33rd Ann. FOCS Symp.(1992) 620-627.
11. A. El Maftouhi and W. Fernandez de la Vega, On random 3-sat, Combin. Probab. Comput. 4 (1995), no. 3, 189–195. MR 1356574, https://doi.org/10.1017/S0963548300001590
12. P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 0125031
13. E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998) 27-35. CMP 99:02
14. Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993–3002. MR 1371123, https://doi.org/10.1090/S0002-9939-96-03732-X
15. Alan Frieze and Svante Janson, Perfect matchings in random 𝑠-uniform hypergraphs, Random Structures Algorithms 7 (1995), no. 1, 41–57. MR 1346283, https://doi.org/10.1002/rsa.3240070104
16. Alan Frieze and Stephen Suen, Analysis of two simple heuristics on a random instance of 𝑘-SAT, J. Algorithms 20 (1996), no. 2, 312–355. MR 1379227, https://doi.org/10.1006/jagm.1996.0016
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. Scott Kirkpatrick and Bart Selman, Critical behavior in the satisfiability of random Boolean expressions, Science 264 (1994), no. 5163, 1297–1301. MR 1275579, https://doi.org/10.1126/science.264.5163.1297
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. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
24. D. Reimer, Butterflies, 1995 (to appear).
25. L. Russo, On the critical percolation probabilities, Z. Wahrsch. werw. Gebiete, 43(1978), 39-48.
26. Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, https://doi.org/10.1007/BF00537230
27. J. Schmidt-Pruzan, E. Shamir, A threshold for perfect matchings in random pure hypergraphs, Combinatorica 5 (1985) 81-94.
28. Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576–1587. MR 1303654