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 $k$-sat problem
HTML articles powered by AMS MathViewer

by Ehud Friedgut and appendix by Jean Bourgain

J. Amer. Math. Soc. 12 (1999), 1017-1054

DOI: https://doi.org/10.1090/S0894-0347-99-00305-7

Published electronically: May 27, 1999

PDF | Request permission

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

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 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 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 10.1016/0097-3165(86)90060-9
Noga Alon and Raphael Yuster, Threshold functions for $H$-factors, Combin. Probab. Comput. 2 (1993), no. 2, 137–144. MR 1249126, DOI 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 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 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 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 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 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 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 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 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 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