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
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 $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.
- J. Bourgain, Generalized Walsh subspaces of $L_{p}$ product spaces, Seminaire d’Analyse Fonctionnel, Ecole Polytechnique, Palaiseau (1979).
- J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, Geom. Funct. Anal. 7 (1997), no. 3, 438–461. MR 1466334, DOI https://doi.org/10.1007/s000390050015
- E. Friedgut, Sharp thresholds of graph properties and the $k$-sat problem, Journal of the A.M.S.
- J. Kahn, G. Kalai, N. Linial, The influence of variables on Boolean functions, Proc. 29th IEEE FOCS 58-80, IEEE, NY (1988).
- G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
- Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI https://doi.org/10.1007/BF00537230
- Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576–1587. MR 1303654
- D. Achlioptas, E. Friedgut, A Threshold for $k$-Colorability, Random Structures and Algorithms 14 (1999) 63-70.
- 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, DOI https://doi.org/10.1016/0097-3165%2886%2990060-9
- Noga Alon and Raphael Yuster, Threshold functions for $H$-factors, Combin. Probab. Comput. 2 (1993), no. 2, 137–144. MR 1249126, DOI https://doi.org/10.1017/S0963548300000559
- 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, DOI https://doi.org/10.1017/s0021900200029326
- Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
- B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI https://doi.org/10.1007/BF02579198
- J. Bourgain, G. Kalai, Influence of variables in product spaces under group symmetries, to appear in GAFA.
- 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
- 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, DOI https://doi.org/10.1137/0215080
- V. Chvatal, B. Reed, Mick gets some. Proc. 33rd Ann. FOCS Symp.(1992) 620-627.
- A. El Maftouhi and W. Fernandez de la Vega, On random $3$-sat, Combin. Probab. Comput. 4 (1995), no. 3, 189–195. MR 1356574, DOI https://doi.org/10.1017/S0963548300001590
- 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 125031
- E. Friedgut, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998) 27-35.
- 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, DOI https://doi.org/10.1090/S0002-9939-96-03732-X
- Alan Frieze and Svante Janson, Perfect matchings in random $s$-uniform hypergraphs, Random Structures Algorithms 7 (1995), no. 1, 41–57. MR 1346283, DOI https://doi.org/10.1002/rsa.3240070104
- Alan Frieze and Stephen Suen, Analysis of two simple heuristics on a random instance of $k$-SAT, J. Algorithms 20 (1996), no. 2, 312–355. MR 1379227, DOI https://doi.org/10.1006/jagm.1996.0016
- A. Goerdt (1992) A threshold for satisfiability. In Math. Foundations of Computer Science (I.M.Havel and V.Koubek eds.) Prague, Poland.
- 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.
- A. Kamath, R. Motwani, K.Palem, P.Spirakis Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture. Proc. 35th FOCS pp. 592-603.
- Scott Kirkpatrick and Bart Selman, Critical behavior in the satisfiability of random Boolean expressions, Science 264 (1994), no. 5163, 1297–1301. MR 1275579, DOI https://doi.org/10.1126/science.264.5163.1297
- M. Kirouris, E. Kranakis and D. Krizanc, Approximating the unsatisfiability threshold of random formulas, in: Algorithms - ESA’ 96, Lecture Notes in Computer Science 1136
- 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.
- G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
- D. Reimer, Butterflies, 1995 (to appear).
- L. Russo, On the critical percolation probabilities, Z. Wahrsch. werw. Gebiete, 43(1978), 39-48.
- Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI https://doi.org/10.1007/BF00537230
- J. Schmidt-Pruzan, E. Shamir, A threshold for perfect matchings in random $d-$pure hypergraphs, Combinatorica 5 (1985) 81-94.
- Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576–1587. MR 1303654
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
Email:
ehudf@math.huji.ac.il
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