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

Friedgut, Ehud ¹   ; Jean Bourgain, appendix by ²

¹ Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel
² School of Mathematics, Institue of Advanced Study, Princeton, New Jersey 08540

Journal of the American Mathematical Society, Tome 12 (1999) no. 4, pp. 1017-1054

Résumé

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.

Détail

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

Bibliographie

[1] Bourgain, J., Kalai, G. Influences of variables and threshold intervals under group symmetries Geom. Funct. Anal. 1997 438 461

[2] Margulis, G. A. Probabilistic characteristics of graphs with large connectivity Problemy Peredači Informacii 1974 101 108

[3] Russo, Lucio An approximate zero-one law Z. Wahrsch. Verw. Gebiete 1982 129 139

[4] Talagrand, Michel On Russo’s approximate zero-one law Ann. Probab. 1994 1576 1587

[5] Aharoni, Ron, Linial, Nathan Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas J. Combin. Theory Ser. A 1986 196 204

[6] Alon, Noga, Yuster, Raphael Threshold functions for 𝐻-factors Combin. Probab. Comput. 1993 137 144

[7] Van Den Berg, J., Kesten, H. Inequalities with applications to percolation and reliability J. Appl. Probab. 1985 556 569

[8] Bollobás, Béla Random graphs 1985

[9] Bollobás, B., Thomason, A. Threshold functions Combinatorica 1987 35 38

[10] Broder, Andrei Z., Frieze, Alan M., Upfal, Eli On the satisfiability and maximum satisfiability of random 3-CNF formulas 1993 322 330

[11] Chao, Ming-Te, Franco, John Probabilistic analysis of two heuristics for the 3-satisfiability problem SIAM J. Comput. 1986 1106 1118

[12] El Maftouhi, A., Fernandez De La Vega, W. On random 3-sat Combin. Probab. Comput. 1995 189 195

[13] Erdős, P., Rényi, A. On the evolution of random graphs Magyar Tud. Akad. Mat. Kutató Int. Közl. 1960 17 61

[14] Friedgut, Ehud, Kalai, Gil Every monotone graph property has a sharp threshold Proc. Amer. Math. Soc. 1996 2993 3002

[15] Frieze, Alan, Janson, Svante Perfect matchings in random 𝑠-uniform hypergraphs Random Structures Algorithms 1995 41 57

[16] Frieze, Alan, Suen, Stephen Analysis of two simple heuristics on a random instance of 𝑘-SAT J. Algorithms 1996 312 355

[17] Kirkpatrick, Scott, Selman, Bart Critical behavior in the satisfiability of random Boolean expressions Science 1994 1297 1301

[18] Margulis, G. A. Probabilistic characteristics of graphs with large connectivity Problemy Peredači Informacii 1974 101 108

[19] Russo, Lucio An approximate zero-one law Z. Wahrsch. Verw. Gebiete 1982 129 139

[20] Talagrand, Michel On Russo’s approximate zero-one law Ann. Probab. 1994 1576 1587